Spoj - Totient extreme
Solution in C++
#include <bits/stdc++.h>
using namespace std;
#define N 10004
int T , t , n;
int us[N];
double all[N];
long long int sol[N];
void euler()
{
for(int i=2;i<=10000;i++)
{
if(us[i])continue;
for(int j=i;j<=10000;j+=i)
{
us[j]=1;
all[j] *= (1-1.0/i)*1.0;
}
}
for(int i=0;i<N;i++)
all[i]*=i;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie();
for(int i=0;i<N;i++)all[i]=1.0;
euler();
sol[1]=1;
for(int i=2;i<N;i++)
{
long long int ret = sol[i-1];
for(int j=1;j<i;j++)
ret+=2*all[i]*all[j];
ret+=all[i]*all[i];
sol[i]=ret;
}
cin>>T;
while(T-- &&cin>>n)
cout<<sol[n]<<"\n";
return 0;
}
0 التعليقات:
إرسال تعليق