Cod sursa(job #1534727)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 23 noiembrie 2015 22:21:19
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX=1e6;
int a[NMAX+3];
bool b[NMAX+3];

int main()
{
    int n,m;
    long long int i,j,limita,ans=0;
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    scanf("%d%d",&n,&m);
    --n;--m;
    limita=max(n,m);
    a[2]=1;
    for(j=4;j<=limita;j+=2)
        a[j]=1;
    for(j=4;j<=limita;j+=4)
        b[j]=1;
    for(i=3;i<=limita;i+=2) {
        if(a[i]==0){
            a[i]=1;
            for(j=(i<<1);j<=limita;j+=i)
                ++a[j];
            long long int abc=1LL*i*i;
            for(j=abc;j<=limita;j+=abc)
                b[j]=1;
        }
    }
    for(i=2;i<=limita;++i)
        if(b[i]==0)
            ans+=1LL*(a[i]&1?1:-1)*(n/i)*(m/i);
    printf("%lld\n",1LL*n*m-ans);
    return 0;
}