Cod sursa(job #1700262)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 9 mai 2016 22:23:13
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;


const int NMAX = 1000505;


int  c[NMAX];
bool k[NMAX];


int main(void) {
    FILE *fi = fopen("mins.in", "r");
    FILE *fo = fopen("mins.out", "w");
    int n, m;
    i64 ans;

    fscanf(fi,"%d%d",&n,&m);
    --n;
    --m;
    ans = 1LL*n*m;

    if(n>m)
        swap(n, m);
    for(int i=2; i<=n; i++) {
        if(!c[i]) {
            for(int j=i; j<=n; j+=i)
                ++c[j];
            for(i64 j=1LL*i*i; j<=n; j+=i*i)
                k[j] = 1;
        }
    }
    for(int i=2; i<=n; i++) {
        if(k[i])
            continue;
        if(c[i]&1)
            ans -= 1LL*(n/i)*(m/i);
        else
            ans += 1LL*(n/i)*(m/i);
    }

    fprintf(fo,"%lld\n", ans);

    fclose(fi);
    fclose(fo);
    return 0;
}