bool prime[31700]; // 31700*31700 > 1000000000int primes[3500];int cnt=0;
// 筛法求素数
{
memset(prime, 1, sizeof(prime)); prime[0]=false; prime[1]=false; int m=31700; for (int i=2; i<m; i++)
if (prime[i]) {
primes[++cnt ]=i; for (int k=i*i; k<m; k+=i) prime[k]=false;
} return;
} 分解质因子
vector <pair <int, int> > primeFactor(int n){ vector < pair <int, int> > v; for(int i=1; primes[i] * primes[i] <= n; i++ ) { int k = 0 ; while ( n %primes[i] == 0 ) { k ++ ; n/=primes[i] ; } if ( k ) v.push_back(make_pair( primes[i], k)); } if (n != 1) v.push_back (pair <int, int> (n, 1)); return v;}
int PHI (int n) // 欧拉函数{ if (n == 1) return 1; int m=n; for(int i=1; primes[i]*primes[i]<=m; i++){ if (m % primes[i] == 0) { n -= (n / primes[i]); do { m /= primes[i]; } while (m % primes[i] == 0); } } if (m != 1) n -= (n / m); return n;}
// 求n的约数vector<pair<int, int> > v = primeFactor(n); // 分解成素数的积vector<int> factor; //存放约数
int sz=v.size(); int bound=1; for(int j=0; j<sz; j++) // 采用数字电路加1法枚举约数 bound*=(v[j].second+1); // 求出最大值bound.. for(int j=0; j<bound; j++) { // 0 ~ bound-1 int fac= 1; int q=j; for(int k=0; q && k<sz; k++) { // 模出每一位取几个 int tt=q % (v[k].second+1); for(int a=0; a< tt; a++) fac*=v[k].first; q/=(v[k].second+1); } factor.push_back(fac); }题目：Longge‘s Problem http://acm.pku.edu.cn/JudgeOnline/problem?id=2480
(提示: 设P是N的因子, 对a属于[1..N], .. 和N的最大公约数是P的a的个数等于PHI(N/P); ) PHI是欧拉函数