Cod sursa(job #1700209)

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


const int NMAX = 1000005;


bool c[NMAX];
int  v[NMAX];
vector<int> prs;


void erat(int lim) {
    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.push_back(2);
    for(int i=3; i<=lim; i+=2)
        if(!c[i])
            prs.push_back(i);
}

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

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

    for(int i=0; i<prs.size() && 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];
        ++v[tmp];
    }
}

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

    for(int i=0; i<prs.size() && 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+=v[tmp];
        else
            ans-=v[tmp];
    }
    return ans;
}


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);

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

    for(int i=2; i<n; ++i)
        get_sets(i);

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

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

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