Cod sursa(job #2167404)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 13 martie 2018 21:31:58
Problema Mins Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
bool pr[1000002];
int prime[80002],nr;
int a,b;
vector<int>v;
int sol[1000002];
void ciur()
{
    for(int i=2;i<=1000000;++i)
        if(!pr[i])
        {
            prime[++nr]=i;
            for(int j=i+i;j<=1000000;j+=i)
                pr[j]=1;
        }
}
int curr;
int vv[8];
void comb(int poz, int k)
{
    if(poz==k)
    {
        int nr=1;
        for(int j=1;j<=k;++j)
            nr*=v[vv[j]-1];
       // g<<'\n';
      //  g<<poz<<" "<<curr<<" "<<nr<<'\n';
        if(poz%2==1)
            sol[curr]-=b/nr;
        else
            sol[curr]+=b/nr;
        return;
    }
    for(int i=vv[poz]+1;i<=v.size();++i)
    {
        vv[poz+1]=i;
        comb(poz+1,k);
    }
}
int main()
{
    ciur();
    f>>a>>b;
    --a;
    --b;
    for(int i=1;i<=a;++i)
        sol[i]=b;
    long long ss=b;
    for(int i=2;i<=a;++i)
    {
        curr=i;
        int nr=i;
        v.clear();
        for(int j=1;prime[j]*prime[j]<=nr;++j)
            if(nr%prime[j]==0)
            {
                v.push_back(prime[j]);
                while(nr%prime[j]==0)
                    nr/=prime[j];
            }
        if(nr>1)
            v.push_back(nr);
      //  g<<i<<" "<<v.size()<<'\n';
        for(int j=1;j<=v.size();++j)
            comb(0,j);
        ss+=sol[i];
    }
    g<<ss<<'\n';
    return 0;
}