Cod sursa(job #861996)

Utilizator misinozzz zzz misino Data 22 ianuarie 2013 07:35:15
Problema Dirichlet Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream>
#define ll long long
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
int mini,i,j,n,m,ok[1000001],c[1000001];
ll sol;
int main()
{
    f>>n>>m;
    --n,--m;
    mini=min(n,m);
    for(i=2;i<=mini;++i)
    if(c[i]==0)
    {
        for(j=i;j<=mini;j+=i)
        ++c[j];
        if(mini/i<i)
        continue;
        for(j=i*i;j<=mini;j+=i*i)
        ok[j]=1;
    }
    sol=(ll)m*n;
    for(i=2;i<=mini;++i)
    if(!ok[i])
    {
        if(c[i]%2)
        sol-=(ll)(n/i)*(m/i);
        else
        sol+=(ll)(n/i)*(m/i);
    }
    g<<sol<<'\n';
    return 0;
}