Cod sursa(job #2118221)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 30 ianuarie 2018 13:09:20
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#define X 1000000000
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
int arr[1000005],s[1000005];
int main()
{
    int n,m,N,i,j;
    long long S;
    in>>n>>m;n--;m--;
    S=1LL*n*m;
    N=min(n,m);
    for(i=2;i<=N;i++)
        arr[i]=1,s[i]=X;
    for(i=2;i*i<=N;i++)
    {
        if(arr[i])
            for(j=i*i;j<=N;j+=i)
                arr[j]=0;
    }
    for(i=2;i<=N;i++)
        if(arr[i])
            for(j=N/i;j>0;j--)
                if(s[j]!=X)
                    s[i*j]=1+s[j];
    for(i=2;i<=N;i++)
        if(s[i]!=X)
    {
        if(s[i]%2)
            S-=1LL*(n/i)*(m/i);
        else
            S+=1LL*(n/i)*(m/i);
    }
    out<<S;
    return 0;
}