Pagini recente » Cod sursa (job #2473428) | Cod sursa (job #1729488) | Cod sursa (job #2284225) | Cod sursa (job #1288796) | Cod sursa (job #1750468)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
const int MAXP=1002;
int m,n,prim[1001],lp=0,lg,t,p[1001],sol,card;
bool b[1005];
void generareNumerePrime()
{
int i,j;
for(i=4; i<MAXP; i+=2)
b[i]=1;
for(i=3; i*i<MAXP; i+=2)
if(b[i] == 0)
for(j = i * i; j < MAXP; j += i)
b[j] = 1;
for(i = 2; i < MAXP; i++)
if(b[i] == 0) prim[++lp] = i;
}
void generareDivizori(int a)
{
lg=0;
for(int j=1; prim[j]*prim[j]<=a; j++)
if(a%prim[j]==0)
{
p[++lg]=prim[j];
while(a%prim[j]==0) a/=prim[j];
}
if(a>1) p[++lg]=a;
}
int main()
{
generareNumerePrime();
f>>m>>n;
m--;
n--;
int minim=min(m,n),maxim=max(m,n);
for(int a=2; a<=minim; a++)
{
generareDivizori(a);
int nt=1<<lg;
card=0;
for(int i=1; i<nt; i++)
{
long long int prod=1;
int j=0,p2,ndiv=0;
while((p2=1<<j)<=i)
{
if(p2&i)
{
prod*=p[j+1];
ndiv++;
}
j++;
}
long long int t=a/prod;
if(ndiv%2==0)
card-=t;
else
card+=t;
}
}
card=card*2-1;
sol=m*n;
sol-=card;
for(int a=minim+1; a<=maxim; a++)
{
generareDivizori(a);
int nt=1<<lg;
card=0;
for(int i=1; i<nt; i++)
{
long long int prod=1;
int j=0,p2,ndiv=0;
while((p2=1<<j)<=i)
{
if(p2&i)
{
prod*=p[j+1];
ndiv++;
}
j++;
}
long long int t=minim/prod;
if(ndiv%2==0)
card-=t;
else
card+=t;
}
}
sol-=card;
g<<sol;
return 0;
}