Cod sursa(job #1212905)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 26 iulie 2014 14:10:18
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <iostream>
#include <bitset>
using namespace std;
bitset < 1112 > viz;
int prime[1102];
inline void Eratosthenes(){
    prime[++prime[0]] = 2;
    for(int i = 3;i < 1100;i += 2)
        if(!viz[i]){
            prime[++prime[0]] = i;
            for(int j=i*i;j <= 1100; j += 2*i)
                viz[j] = 1;
        }
}
inline int Cnt(int x){
    int d = 2;
    int step = 1;
    int ret = 0;
    while(d*d <= x){
        if(x%d==0){
            ++ret;
            while(x%d==0)
                x /= d;
        }
        ++step;
        d = prime[step];
    }
    if(x>1)
        ++ret;
    return ret;
}
int main(){
    int n,m;
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    cin >> n >> m;
    --n,--m;
    int minn = min(n,m);
    Eratosthenes();
    long long sol = 1LL*n*m;
    long long nr = 0;
    for(int i=2;i<=minn;++i)
        if(Cnt(i)&1)
            nr += 1LL*(n/i)*(m/i);
        else
            nr -= 1LL*(n*i)*(m/i);
    sol -= nr;
    cout<<sol<<"\n";
    return 0;
}