Cod sursa(job #1118548)

Utilizator andrettiAndretti Naiden andretti Data 24 februarie 2014 11:52:21
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 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); sieve[i]++;
         for(int j=i;1LL*i*j<=Min;j++)
          if( (1LL*i*j)%(1LL*i*i)!=0)
           sieve[i*j]++;
          else sieve[i*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;
}