相关题目:
POJ2407、POJ2478、POJ3090、POJ3696
详细信息参考其他关于欧拉函数的资料。
欧拉递推公式:
用factor记录某个数是否是质数,如果不是则记录其最小质因子。
若(N%a==0 && (N/a)%a==0) 则E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则E(N)=E(N/a)*(a-1);
const int maxn = 1000; int factor[maxn+5]; int prime[maxn+5]; int pct; int e[maxn+5]; void init() { int i, j; memset(factor, 0, sizeof(factor)); pct = 0; factor[0] = factor[1] = 1; for (i=2; i<=maxn; i++) { if (factor[i]==0) prime[pct++] = i; for (j=0; j<pct && i*prime[j]<=maxn && (prime[j]<=factor[i] || factor[i]==0); j++) { factor[i*prime[j]] = prime[j]; if (i%prime[j]==0) break; } } } void getEuler() { int i, d; for (i=2; i<=maxn; i++) { if (factor[i]==0) { e[i] = i-1; } else { d = i/factor[i]; if (d%factor[i]==0) { e[i] = e[d] * factor[i]; } else { e[i] = e[d] * (factor[i]-1); } } } e[1] = 0; }
直接求某数的欧拉值:
int Euler(int n) { int i, res = n; for (i=2; i*i<=n; i++) { if (n%i==0) { n /= i; res -= res/i; while(n%i==0) n /= i; } } if (n>1) res -= res/n; return res; }
P.S.
对于较大的数的快速幂取模需要用到乘法取模:
__int64 mmod(__int64 a,__int64 b,__int64 n)//乘法取模 { a %= n; __int64 res = 0; while(b) { if(b&1) { res += a; if(res>=n) res -= n; } a <<= 1; if(a>=n) a -= n; b >>= 1; } return res; } __int64 exmod(__int64 a,__int64 b,__int64 n)//快速幂取模 { a %= n; __int64 res = 1; while(b>=1) { if(b&1) res = mmod(res, a, n); a = mmod(a, a, n); b >>= 1; } return res; }
解题报告:
POJ2407:最简单的欧拉函数
POJ2478、POJ3090:求某数范围内互质的对数。POJ3090需要注意开始的一些特殊值,同时需要特别处理一下。
POJ3696:求解10^x = 1 (mod 9*L/gcd(L,8))的满足x>0的最小解。其中x=Euler(9*L/gcd(L,8))。枚举x的因子时只需枚举到其根号。同时使用快速幂取模。