poj3090 Visible Lattice Points

2019-11-08 01:46:52

字体：大中小

来源：转载

供稿：网友

http://poj.org/PRoblem?id=3090 题目

题解

求phi（1）到phi（n）的和

代码

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;int prime[5800000],fai[10001000],tot;bool Notprime[10001000]; int main(){ int t,n; scanf("%d",&t); fai[1]=1; for(int i=2;i<=10000000;i++) { if(Notprime[i]==false) prime[++tot]=i,fai[i]=i-1; for(int j=1;j<=tot,i * prime[j] <= 10000000;j++) { Notprime[i*prime[j]]=true; if(i%prime[j]==0) { fai[i*prime[j]]=prime[j]*fai[i]; break; }else fai[i*prime[j]]=(prime[j]-1)*fai[i]; } } for(int i = 1;i <= t;i++){ scanf("%d",&n); long long ans=0; for(int j = 1;j <= n;j++)ans += fai[j]; ans = ans * 2 + 1; printf("%d %d %I64d/n",i,n,ans); } return 0;}

上一篇：Arrays.toList(T[] t)返回的List不可执行add方法

下一篇：三极管之——PNP与NPN