Cod sursa(job #1118578)

Utilizator andrettiAndretti Naiden andretti Data 24 februarie 2014 11:59:27
Problema Mins Scor 80
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(int j=1;1LL*i*j<=Min;j++)
          if((1LL*i*j)%(1LL*i*i)==0) sieve[i*j]=-inf;
          else sieve[i*j]++;
     }
     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;
}