求一个做烧肉的网站,淘宝联盟 网站怎么做,做英文网站挂谷歌广告,涿州网站建设涿州传送阵#xff1a;NEFU2022-Eulers totient function - Virtual Judge
思路#xff1a;
对于一个小于1的数#xff0c;化为二进制#xff0c;找第一次进入循环的位置和最小循环周期。
我们设第一次进入循环的位置是i#xff0c;第一次循环结束后#xff0c;再次进入循…传送阵NEFU2022-Eulers totient function - Virtual Judge
思路
对于一个小于1的数化为二进制找第一次进入循环的位置和最小循环周期。
我们设第一次进入循环的位置是i第一次循环结束后再次进入循环的位置是j;
循环周期为j-i
先将分母分子化为最简式p/q。
由i,j定义可得p*2^ip*2^j(mod q)
移位得p*2^i(2^(j-i)-1)0(mod q)
由于p,q互素得2^i(2^(j-i)-1)0(mod q)
可以得到iq能整除2最多次数;
iq能整除2最多次数(i取最小)
q1q/2^i
2^(j-i)1(mod q1)
根据欧拉函数phi(q1)为方程一个解但不一定是最小
我们可以便利phi(q1)因子找到最小满足方程的因子k,那么j-ik
代码
#define _CRT_SECURE_NO_WARNINGS #includeiostream #includecstdio #includecstdlib #includestring #includecstring #includecmath #includectime #includealgorithm #includeutility #includestack #includequeue #includevector #includeset #includemath.h #includemap using namespace std; typedef long long LL; typedef unsigned long long ull; #define per(i,a,b) for(int ia;ib;i) #define ber(i,a,b) for(int ia;ib;i--) const int N 1e5 3; LL d; int o[N], cnt; LL a, b; char c; int cn 0; LL exgcd(LL a, LL b) { if (!b) return a; return exgcd(b, a % b); } LL seek(LL x) { LL ans x; for (LL i 2; i * i x; i) { if (x % i 0) ans ans / i * (i - 1); while (x % i 0) x / i; } if (x 1) ans ans / x * (x - 1); return ans; } int check(LL a,LL b,LL mod) { LL ans 1; while (b) { if (b 1) ans a * ans % mod; b 1; a a * a % mod; } return ans 1; } LL sek(LL y) { cnt 0; for (LL i 1; i * i y; i) { if (y % i 0) { o[cnt] i; o[cnt] y / i; } } sort(o 1, o 1 cnt); for (int i 1; i cnt; i) { if (check(2, o[i], b)) { return o[i]; } } return y; } int main() { ios::sync_with_stdio(false); while (scanf(%lld%c%lld, a, c, b) ! EOF) { cn; if (a 0) { printf(Case #%d:, cn); printf( %d,%d\n, 1, 1); continue; } dexgcd(a, b); a / d; b / d; LL i 0, j 0; while (b % 2 0) { b / 2; i; while (a b) a - b; } i; j seek(b); LL k sek(j); printf(Case #%d:, cn); printf( %lld,%lld\n, i, k); } return 0; }
