Cod sursa(job #1316044)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 ianuarie 2015 14:37:33
Problema Mins Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define MAXN 1000000
int c[MAXN+1];
int main(){
    int a, b, n, i, j;
    long long ans;
    FILE *fin, *fout;
    fin=fopen("mins.in", "r");
    fout=fopen("mins.out", "w");
    fscanf(fin, "%d%d", &a, &b);
    a--;
    b--;
    if(a<=b){
        n=a;
    }else{
        n=b;
    }
    ans=a*(long long)b;
    for(i=2; i<=n; i++){
        if(c[i]==0){
            for(j=i; j<=n; j+=i){
                c[j]++;
            }
            if(i*(long long)i<=n){
                for(j=i*i; j<=n; j+=i*i){
                    c[j]=-1;
                }
            }
        }
        if(c[i]!=-1){
            if(c[i]%2==1){
                ans-=(a/i)*(long long)(b/i);
            }else{
                ans+=(a/i)*(long long)(b/i);
            }
        }
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}