Pagini recente » Diferente pentru onis-2016/solutii-runda-2 intre reviziile 18 si 25 | Cod sursa (job #2012448) | Cod sursa (job #2016391) | Cod sursa (job #2277584) | Cod sursa (job #1607664)
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream si("mins.in");
ofstream so("mins.out");
bitset<1005> erat;
int cont;
int nrpr[170];
void ciur()
{
cont=1;
nrpr[0]=2;
int i,j,k;
for(i=3;i<1005;i+=2)
{
if(!erat[i])
{
nrpr[cont]=i;
k=i+i;
++cont;
for(j=i+k;j<1005;j+=k)
erat[j]=1;
}
}
}
int nrd,diviz[170];
int prod;
long long sol;
void backt(int a,int k,int lim,int s)
{
if(k!=1)
{
sol+=s*(a/prod);
}
if(k>nrd)
return;
int i;
for(i=lim;i<nrd;++i)
{
prod*=diviz[i];
if(prod>a)
{
prod/=diviz[i];
return;
}
backt(a,k+1,i,-s);
prod/=diviz[i];
}
}
int main()
{
ciur();
int n,m;
si>>n>>m;
--m;
int a;
int x,r;
long long sum=0;
for(x=1;x<n;++x)
{
r=x;
nrd=0;
for(a=0;nrpr[a]<x&&nrpr[a]<m;a++)
{
if(x%nrpr[a]==0)
{
diviz[nrd]=nrpr[a];
nrd++;
while(x%nrpr[a]==0)
{
x/=nrpr[a];
}
}
}
if(x!=1)
{
diviz[nrd]=x;
++nrd;
}
sol=0;
prod=1;
backt(m,1,0,-1);
x=r;
sum+=m-sol;
}
so<<sum<<'\n';
return 0;
}