http://poj.org/problem?id=3090
預處理答案 ans[i]比ans[i-1]多出來的部分 就是2*f(i) 也就是看多出來的一圈點中有多少點與(0,0)的橫縱坐标之差互質 畫畫圖就出來了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
int ans[maxn];
int solve(int n)
{
int i,res;
res=n;
for(i=2;i*i<=n;i++){
if(n%i==0){
res=res*(i-1)/i;
while(n%i==0){
n/=i;
}
}
}
if(n!=1){
res=res*(n-1)/n;
}
return res;
}
void init()
{
int i,j;
ans[1]=3;
for(i=2;i<=1e3;i++){
ans[i]=ans[i-1]+2*solve(i);
}
}
int main()
{
int t,cas,n;
init();
scanf("%d",&t);
for(cas=1;cas<=t;cas++){
scanf("%d",&n);
printf("%d %d %d\n",cas,n,ans[n]);
}
return 0;
}