Pagini recente » Clasament proba123451 | Cod sursa (job #1508273) | Cod sursa (job #2814492) | Cod sursa (job #2167404)
#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;
}