欧拉定理：若正整数 a,ma,ma,m 互质，则 aφ≡1a^{φ}≡1aφ≡1 其中 φφφ 是欧拉函数， 欧拉函数：φφφ，表示的是1 ~ n 之间与n互质的数的个数，思考一下，我们给定的m是一个质数，质数的欧拉函数是多少呢？
总所周知，莱昂哈德·欧拉（Leonhard Euler %%%）是一个数学大佬，对数学、力学、几何学等等有着非常突出的贡献。我们可以在各种地方看到各种的欧拉公式，欧拉定理，欧拉函数，欧拉回路... 总所不周知，繁凡さん很喜欢翻论文，翻各种奇怪的博客，学各种奇怪的算法。有一天，他在划水的时候发现了一个有趣的论文： “看到让欧拉出丑，我啪的一下就点进去了，很快啊。” 嗷，原来是昨天（18世纪），有几个年轻人，他们说，“ 额... 欧拉老师，我们给你一个奇点，咱就叫他欧拉奇点，我们设 mmm 是正整数，aaa 是整数，如果说这个 aaa 模 mmm 的阶等于 φ(m)φ(m)φ(m) ，则称 aaa 为模 mmm 的一个欧拉奇点。（其中 φ(m)φ(m)φ(m) 表示 mmm 的欧拉函数）。我们今天来呢，就是让给您 111 个质数 mmm ，想请您找出 mmm 最小的欧拉奇点 ”。 欧拉老师不讲武德，准备让你来解决这个问题。 不过我讲武德，所以我会告诉你一些信息，以帮助你完成这个问题： 设a,ma, ma,m 是整数，且aaa 和 mmm 互质，那么：使 ax≡1(mod m)a^x≡1(mod m)ax≡1(mod m) 成立的最小正整数 xxx 叫做 aaa 模 mmm 的阶，ax≡1(mod m)a^x≡1(mod m)ax≡1(mod m)的意思就是ax%m=1% m=1a^x% m = 1 % m=1ax%m=1% m=1。 当然，这里的数都太大了，你如果想要求abmod ca^b mod cabmod c，你可以直接使用下面的代码： int qpow(int a, int b, int c) { int res = 1; while(b){ if(b & 1) res = ((long long)res * a) % c; a = ((long long)a * a) % c; b >>= 1; } return res % c; } 欧拉定理：若正整数 a,ma,ma,m 互质，则 aφ(m)≡1(mod m)a^{φ(m)}≡1(mod m)aφ(m)≡1(mod m) 其中 φ(m)φ(m)φ(m) 是欧拉函数。 欧拉函数：φ(n)φ(n)φ(n)，表示的是1 ~ n 之间与n互质的数的个数。思考一下，我们给定的m是一个质数，质数的欧拉函数是多少呢？ m - 1 ！ 我们根据上面的几个提示，可以很容易地发现， aaa 模 mmm 的阶一定能整除 φ(m)φ(m)φ(m)，即aaa 模 mmm 的阶一定是φ(m)φ(m)φ(m)的因数，或者就是φ(m)φ(m)φ(m)他本身，也就是说我们只需要考虑依次枚举小于他的数，根据题意判断是不是φ(m)φ(m)φ(m)即可~。
