Cod sursa(job #1065324)

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

using namespace std;

const int N=1000005;

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

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

int main()
{
    int n, m, mins;
    long long 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])
            {
                for(j=i+i;j<=mins;j+=i) d[j]++;
                for(j=i*i;j<=mins;j+=i*i) v[j]=1;
            }
            if(d[i]%2) sol+=(n/i)*(m/i);
            else sol-=(n/i)*(m/i);
        }
    }
    fout<<sol;
}