P4995 - Moodular Arithmetic

内存限制：256 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：3 通过：3

就像任何一个聪明的学生一样，凯文·孙(Kevin Sun)在波维尼亚州立大学(BGU)师从农民伊万(Farmer Ivan)，学习心理学、豇豆学和密码学。在他的奥数(MoO)课上，凯文遇到了一个奇怪的函数方程，需要你的帮助。对于两个固定整数k和p，其中p是一个奇素数，泛函方程表示
对于某个函数。(这个方程适用于0到p-1范围内的任何整数x。)
事实上f可以是很多不同的函数。凯文不想求解，而是想让你数出满足这个方程的不同函数f的个数。因为答案可能很大，你应该对109+7取模输出结果。

The input consists of two space-separated integers p and k (3≤p≤1000000, 0≤k≤p-1) on a single line. It is guaranteed that p is an odd prime number.

Print a single integer, the number of distinct functions f modulo 10⁹+7.

5 4

In the first sample, p=3 and k=2. The following functions work:

f(0)=0, f(1)=1, f(2)=2.
f(0)=0, f(1)=2, f(2)=1.
f(0)=f(1)=f(2)=0.

603B 1800 combinatorics, dfs and similar, dsu, math, number theory

4995: Moodular Arithmetic

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签