首页 > 代码库 > UVA 11426 GCD - Extreme (II)
UVA 11426 GCD - Extreme (II)
题目大意：
求出
我们可以通过求∑(1<=i<=N)∑(1<=j<=N)gcd(i,j) 然后减去 i ， j相同的情况，最后因为 i ， j 互换取了两次所以除以2
上述式子等于 ∑(1<=i<=N)∑(1<=j<=N)∑(d|gcd(i,j))phi[d] phi[d] 是欧拉函数
∑phi[d]∑∑(1<=i<=N/d)∑(1<=j<=N/d)
#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define ll long longconst int N = 4000010;int prime[N] , phi[N] , tot;bool vis[N];void get_phi(){ memset(vis , 0 , sizeof(vis)); tot = 0 , phi[1] = 1; for(int i=2 ; i<=4000000 ; i++){ if(!vis[i]) prime[tot++] = i , phi[i] = i-1; for(int j=0 ; j<tot ; j++){ if(i*prime[j]>4000000) break; vis[i*prime[j]]=true; if(i%prime[j] == 0){ phi[i*prime[j]] = phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } }}int main(){ // freopen("a.in" , "r" , stdin); get_phi(); int n; while(scanf("%d" , &n) , n) { ll ans = 0; for(int d=1 ; d<=n ; d++){ ans = ans+(ll)(n/d)*(n/d)*phi[d]; ans = ans - d; } printf("%lld\n" , ans/2); } return 0;}
UVA 11426 GCD - Extreme (II)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。