Cod sursa(job #1213028)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 26 iulie 2014 22:25:45
Problema Mins Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 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){
        int f;
        if(x%d==0){
            ++ret;
            f = 0;
            while(x%d==0){
                x /= d;
                ++f;
            }
            if(f>1)
                return -1;
        }
        ++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){
        int x = Cnt(i);
        if(x>0){
            if(x&1)
                nr += 1LL*(n/i)*(m/i);
           else
                nr -= 1LL*(n/i)*(m/i);
        }
    }
    sol -= nr;
    cout<<sol<<"\n";
    return 0;
}