|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <stdio.h> #include <string.h> #include <ctype.h> #include <vector> #include <queue> using namespace std; #define MAXN 10005 vector<int> decomp(int n){ vector<int> res; for (int i = 2; i <= n; i++) { if (n % i == 0) { res.push_back(i); n /= i; i = 1; } } return res; } int main(){ int toQuery = 0; while (cin >> toQuery) { vector<int> dec = decomp(toQuery); sort(dec.begin(), dec.end()); dec.erase(unique(dec.begin(), dec.end()),dec.end()); for (int i = 0; i < dec.size(); i++) { toQuery *= dec[i]-1; toQuery /= dec[i]; } cout << toQuery << endl; } } |
这个题是欧拉函数：http://baike.baidu.com/view/107769.htm，正好就是这货的定义，说实话我都不知道欧拉函数是啥，打表又没意思了。。。
简单的说就是这个数挨个乘上(n-1)/n，n是不同的质因数。
贴一个求欧拉函数更好的姿势：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ll phi(ll n) { ll m=(ll)sqrt(n+0.5),ans=n; for(ll i=2;i<=m;i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0)n/=i; } } if(n>1)ans=ans/n*(n-1); return ans; } |
降幂公式 a^b %c= a^(b%phi(c)+phi(c)) %c （b>=phi(c)）
这个是意外收获，可以用到欧拉函数的地方。
