Nu aveti permisiuni pentru a descarca fisierul grader_test1.ok
Cod sursa(job #341744)
Utilizator | Data | 19 august 2009 14:03:35 | |
---|---|---|---|
Problema | Mins | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.75 kb |
#include<stdio.h>
#define N 1000100
long long n,m,i,j,p[N],pp[N],s[N],sol;
void read(),solve();
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%lld%lld",&n,&m);
if(n<m)n^=m^=n^=m;
}
void solve()
{
p[1]=1;s[1]=1;
for(i=2;i<m;i++)
{
if(p[i])continue;p[i]=i;
for(j=i*i;j<m;j+=i)p[j]=i;
for(j=i*i;j<m;j+=i*i)pp[j]=i;
}
m--;n--;sol+=m*n;
for(i=2;i<=m;i++)
{
if(pp[i])continue;
s[i]=-s[i/p[i]];
sol+=s[i]*(m/i)*(n/i);
}
printf("%lld\n",sol);
}