Cod sursa(job #338495)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 5 august 2009 20:50:45
Problema Mins Scor Ascuns
Compilator cpp Status done
Runda Marime 1.84 kb
#include <stdio.h>
#include <math.h>

#define maxn 500010
#define maxnr 500010

using namespace std;

long n, m, r, nr, pr, sum, d, x, wq, j, div;
long long sol;
long dp[maxnr], f[maxnr], num[maxn];
char ciur[maxnr];
long i, l, nrb, ndp;

int main()
{
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    n--;
    m--;
    if(n>m)
    {
        sol=n;
        n=m;
        m=sol;
    }
    sol=0;
    r=(long) sqrt(m);
    for(i=2; i<=m; i++)
    {
        if(ciur[i]==0)
        {
            wq++;
            num[wq]=i;
            if(i<=r )
            {
                for(j=i*i; j<=m; j+=i)
                {
                    ciur[j]=1;
                }
            }
        }
    }
    for(i=1; i<=m; i++)
    {
        sum=0;
        x=i;
        
        d=0;
        nr=0;
        r = (long)sqrt(x);
        
        while(x>1 && num[d]<=r)
        {
            d++;
            div=num[d];
            if(x % div==0)
            {
                nr++;
                dp[nr]=div;
                while(x % div == 0)
                {
                    x/=div;
                }
            }
        }
        if(x>1)
        {
            nr++;
            dp[nr]=x;
        }
        
        for(j=0; j<(1<<nr); j++)
        {
            nrb=0;
            pr=1;
            for(l=0; l<nr; l++)
            {
                if( ((1<<l) & j))
                {
                    nrb++;
                    pr*=dp[l+1];
                }
            }
            if(nrb%2==0)
            {
                sum+=n/pr;
            }
            else
            {
                sum-=n/pr;
            }
        }
        sol+=sum;                    
    }
    printf("%lld\n", sol);
    return 0;
}