Cod sursa(job #1108905)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 16 februarie 2014 15:06:11
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
using namespace std;
#include <fstream>
#define NMAX 1000005
ifstream fin("mins.in");
ofstream fout("mins.out");
int N,M,C,D;
long tot[NMAX];
long long S;
int GCD(int A,int B)
{
    if(!B)
        return A;
    return GCD(B,A%B);
}
int main(void)
{
    int i, j;
    fin>>C>>D;
    N=max(C,D);
    M=min(C,D)-1;
    for(i=1;i<=M;i++)
        tot[i]=i;
    for (i = 2; i <= M; ++i)
        if (tot[i]==i)
        {
            tot[i]=i-1;
            for (j = i+i; j <= M; j += i)
                tot[j]=tot[j]/i*(i-1);
        }
    for(i=1;i<=M;i++)
        S=S+1LL*tot[i];

    S=2*S-1;
    for(int i=M;i<N;i++)
        for(int j=1;j<M;j++)
            if(GCD(i,j)==1)
                    S++;
    fout<<S<<"\n";
    return 0;
}