Cod sursa(job #1118602)

Utilizator andrettiAndretti Naiden andretti Data 24 februarie 2014 12:06:59
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<algorithm>
#define maxn 1000005
#define inf 0x3f3f3f3f
using namespace std;

int n,m,Min;
int sieve[maxn];
long long sol;

void read()
{
    scanf("%d%d",&n,&m);
    n--; m--; Min=min(n,m);
}

void solve()
{
    sol=1LL*n*m;
    for(int i=2;i<=Min;i++)
     if(!sieve[i])
     {
         sol-=1LL*(n/i)*(m/i);
         for(long long j=i;j<=Min;j+=i) sieve[j]++;
         for(long long j=1LL*i*i;j<=Min;j+=1LL*i*i) sieve[j]=-inf;
     }
     else
     if(sieve[i]>1)
     {
        if(sieve[i]%2==0) sol+=1LL*(n/i)*(m/i);
        else sol-=1LL*(n/i)*(m/i);
     }
}

int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);

    read();
    solve();
    printf("%lld",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}