Cod sursa(job #1736699)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 2 august 2016 14:35:27
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
#include<algorithm>
#define MAXN 1100000
using namespace std;
int dp[MAXN],ok[MAXN];
int main(){
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    int n,m,value,i,j;
    long long answer;
    scanf("%d%d",&n,&m);
    if(n>m)
        swap(n,m);
    n--;
    m--;
    answer=1LL*n*m;
    for(i=2;i<=n;i++){
        if(dp[i]==0){
            if(1LL*i*i<=n)
                value=i*i;
            else
                value=n+1;
            for(j=i;j<=n;j+=i){
                dp[j]++;
                if(j%value==0)
                    ok[j]=1;
            }
        }
        if(ok[i]==1)
            continue;
        if(dp[i]%2==1)
            answer=answer-1LL*(n/i)*(m/i);
        else
            answer=answer+1LL*(n/i)*(m/i);
    }
    printf("%lld",answer);
    return 0;
}