昆明百度推广开户费用,网站seo诊断工具,wordpress代码实现下载文件,罗湖网站建设报价在数论#xff0c;对正整数n#xff0c;欧拉函数是小于或等于n的正整数中与n互质的数的数目#xff08;不包括1#xff09; 题目 思路
有三个点比较特殊#xff08;因为一来这三个点一定可见#xff0c;同时也无法用gcd 1判断#xff09;#xff1a;#xff08;0对正整数n欧拉函数是小于或等于n的正整数中与n互质的数的数目不包括1 题目 思路
有三个点比较特殊因为一来这三个点一定可见同时也无法用gcd 1判断01、10、11对于其他点我们发现只要 g c d ( x , y ) 1 gcd(x,y) 1 gcd(x,y)1那就可见有一类特例就是 x y x y xy但是也无妨因为欧拉函数不算1算自身我们可以看作不算自身算1我们对称地考虑考虑 x y x y xy的情况枚举 x x x计算欧拉函数的值累加最后乘2注意加上上面的三个特例如何计算欧拉函数呢 做法一就是利用质因数分解这个比较麻烦每次使用都要调用计算做法二在欧拉筛的过程中进行计算分为四类处理 处理 φ ( 1 ) 1 \varphi(1) 1 φ(1)1处理 φ ( p ) p − 1 , p i s a p r i m e \varphi(p) p-1\;,\; p \;is \;a \;prime φ(p)p−1,pisaprime处理 φ ( z ∗ p ) φ ( z ) ⋅ p , z m o d p 0 \varphi(z*p) \varphi(z) \cdot p\;,\; z \mod p 0 φ(z∗p)φ(z)⋅p,zmodp0 φ ( z ∗ p ) \varphi(z*p) φ(z∗p) 起手的 n n n 比 φ ( z ) \varphi(z) φ(z)多了 p 处理 φ ( z ∗ p ) φ ( z ) ⋅ ( p − 1 ) , z m o d p ≠ 0 \varphi(z*p) \varphi(z) \cdot (p-1)\;,\; z \mod p \neq0 φ(z∗p)φ(z)⋅(p−1),zmodp0 φ ( z ∗ p ) \varphi(z*p) φ(z∗p) 起手的 n n n 比 φ ( z ) \varphi(z) φ(z)多了 p同时还要考虑一个新的质因数 p p p 代码
质因数分解版
#include bits/stdc.h
using namespace std;
const int N 1010;
int get_phi(int n)
{int ans n;for(int i 2; i*i n; i){if(n % i 0){ans ans * (i-1) / i;while(n % i 0) n / i;}}if(n 1) ans ans * (n-1) / n;return ans;
}int main()
{int t;cin t;int cnt 0;while(t--){int n;cin n;int res 3;for(int x 2; x n; x){res 2*get_phi(x);}cout cnt n res \n;}return 0;
}欧拉筛版
#include bits/stdc.h
using namespace std;
const int N 1010;
int primes[N], idx;
bool st[N];
int phi[N];
void get_primes(int n)
{phi[1] 1;for(int i 2; i n; i){if(!st[i]){primes[idx] i;phi[i] i-1;}for(int j 1; primes[j]*i n; j){st[primes[j]*i] true;if(i % primes[j] 0){phi[primes[j]*i] phi[i] * primes[j];break;}phi[primes[j]*i] phi[i] * (primes[j] - 1);}}
}
int main()
{get_primes(1000);int t;cin t;int cnt 0;while(t--){int n;cin n;int res 3;for(int x 2; x n; x){res 2*phi[x];}cout cnt n res \n;}return 0;
}
