Cod sursa(job #1065326)

Utilizator andreiiiiPopa Andrei andreiiii Data 23 decembrie 2013 10:13:36
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <algorithm>
#include <fstream>
#include <bitset>

using namespace std;

const int N=1000005;

ifstream fin("mins.in");
ofstream fout("mins.out");

long long d[N];
bitset <N> v;

int main()
{
    long long n, m, mins, i, j, sol;
    fin>>n>>m;
    n--; m--;
    sol=1LL*n*m;
    mins=min(n, m);
    for(i=2;i<=mins;i++)
    {
        if(!v[i])
        {
            if(!d[i])
            {
                sol-=(n/i)*(m/i);
                for(j=i+i;j<=mins;j+=i) d[j]++;
                for(j=i*i;j<=mins;j+=i*i) v[j]=1;
            }
            else if(d[i]%2) sol-=(n/i)*(m/i);
            else sol+=(n/i)*(m/i);
        }
    }
    fout<<sol;
}