Cod sursa(job #1700213)

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


const int NMAX = 1000005;


bool c[NMAX];
int  v[NMAX],
   prs[NMAX];

int n, m;


void erat(int lim) {
    int top=0;
    c[0] = 1;
    c[1] = 1;
    for(int i=4; i<=lim; i+=2)
        c[i] = 1;

    for(int i=3; i*i<=lim; i+=2) {
        if(c[i])
            continue;
        for(i64 j=i*i; j<=lim; j+=i+i)
            c[j] = 1;
    }
    prs[top++]=2;
    for(int i=3; i<=lim; i+=2)
        if(!c[i])
            prs[top++]=i;
}

inline int cbits(int arg) {
    int ans = 0;
    while(arg) {
        if(arg&1)
            ++ans;
        arg>>=1;
    }
    return ans;
}

inline int pinex(int arg) {
    int fct[15];
    int tmp,
        ans = 0,
        top = 0;

    for(int i=0; 1LL*prs[i]*prs[i]<=arg; ++i) {
        if(arg%prs[i])
            continue;
        while(!(arg%prs[i]))
            arg/=prs[i];
        fct[top++] = prs[i];
    }
    if(arg>1)
        fct[top++] = arg;
    for(int i=1; i<(1<<top); ++i) {
        tmp = 1;
        for(int j=0; (1<<j)<=i; ++j)
            if(i&(1<<j))
                tmp *= fct[j];
        if(cbits(i)&1)
            ans+=(n-1)/tmp;
        else
            ans-=(n-1)/tmp;
    }
    return ans;
}


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

    fscanf(fi,"%d%d",&n,&m);

    ans = (1LL*n-1)*(m-1);
    erat(max(n, m));
    if(m>n)
        swap(n, m);

    for(int i=2; i<m; ++i)
        ans-=pinex(i);

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

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