Cod sursa(job #2136652)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 20 februarie 2018 08:46:15
Problema Mins Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
using namespace std;
int v[10],prd[1050],cont[1050];
int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    int m ,n;
    int i,j;
    scanf("%d%d",&m,&n);
    long long prod=1LL*(m-1)*(n-1);
    for(i=2;i<m;i++)
    {
        int cnt=0;
        prd[cnt]=1;
        cont[cnt]=0;
        int d=2,e=0,k=i;
        while(k%2==0)
        {
            k/=2;
            e++;
        }
        if(e)
        {
            prd[++cnt]=2;
            cont[cnt]=1;
        }
        d=3;
        while(d*d<=k&&k>1)
        {
            e=0;
            while(k%d==0)
            {
                k/=d;
                e++;
            }
            if(e)
            {
                for(j=cnt;j>=0;j--)
                {
                    prd[++cnt]=prd[j]*d;
                    cont[cnt]=cont[j]+1;
                }
            }
            d+=2;
        }
        if(k>2)
        {
            d=k;
            for(j=cnt;j>=0;j--)
                {
                    prd[++cnt]=prd[j]*d;
                    cont[cnt]=cont[j]+1;
                }
        }
        long long l=0;
        for(j=1;j<=cnt;j++)
        {
            if(cont[j]%2==1)l+=(n-1)/prd[j];
            else
                l-=(n-1)/prd[j];
        }
        prod-=l;
    }
    printf("%lld",prod);
    return 0;
}