Cod sursa(job #1415571)

Utilizator marion4Maria Ionu marion4 Data 5 aprilie 2015 04:48:12
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX=1000000;

int ciur[MAX+1];
bool put[MAX+1];
int c,d;

int main()
{
    FILE *in, *out;
    in=fopen("mins.in","r");
    out=fopen("mins.out","w");
    fscanf(in, "%d%d", &c, &d);
    c--;
    d--;
    int lmax=min(c,d);
    int i,j;
    long long sol=1LL*c*d;

    for (i=2;i<=lmax;++i)
    {
        if(!ciur[i])
        {
            for (j=i;j<=lmax;j+=i)
                ciur[j]++;
            if (1LL*i*i<=lmax)
                for (j=i*i;j<=lmax;j+=i*i)
                    put[j]=true;
        }
    }
    for (i=2;i<=lmax;++i)
        if (put[i]==false)
        {
            if (ciur[i]%2)
                sol-=1LL*(c/i)*(d/i);
            else
                sol+=1LL*(c/i)*(d/i);
        }
    fprintf(out, "%lld", sol);
    return 0;
}