Cod sursa(job #281467)
Utilizator | OLARU SABIN zoltrix | Data | 14 martie 2009 22:49:37 |
---|---|---|---|
Problema | Fractii | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.69 kb |
#include <stdio.h>
#include <fstream.h>
char s[10001];
int t[10001];
int main ()
{
long double nrf;
int i ,j, q, n;
ifstream f("fractii.in");
ofstream g ("fractii.out");
f>>n;
nrf=1;
t[1]=1;
for(i=2;i<=n;i++)
{
if(s[i]==0)
{
t[i]=i-1;
if(i<=n/i+1)
for(j=i*i; j<=n; j*=i)
t[j]=t[j/i]*i;
for(j=i*2; j<=n; j+=i)
{
s[j]=1;
for(q=i; q<=n && j%q==0; q*=i)
if(!t[j] && (j/i)%q!=0)
t[j]=t[q]*t[j/q];
}
}
nrf+=2*t[i];
}
g<<nrf;
return 0;
}