Pagini recente » Cod sursa (job #2762751) | Cod sursa (job #1742888) | Cod sursa (job #2539205) | Cod sursa (job #239003) | Cod sursa (job #1251975)
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
const int NMAX = 1000000;
const int PMAX = 1000;
bool ciur[PMAX+2];
int pr[PMAX+1], pr_ind= 0;
void ciurul() { /// Ciurul pana la 1000(Y_MAX=1000000)... Ce mai ramane din Y e PRIM
int lim= (int)sqrt( 1.0*PMAX );
for( int i= 2; i<=lim; ++i ) {
if( !ciur[i] ) {
pr[ ++pr_ind ]= i;
for( int j= i*i; j<=PMAX; j+=i ) ciur[j]= 1;
}
}
for( int i= lim+1; i<=PMAX; ++i ) {
if( !ciur[i] ) pr[ ++pr_ind ]= i;
}
}
int PINEX( int X, int Y ) { /// Cate numere <= X sunt prime cu Y
if( Y==1 ) return X; /// Toate numerele mai mici sau egale cu X sunt prime cu 1
int p[PMAX+1], R= 0, ind= 1, lim= (int)sqrt(1.0*Y);
/// Descompun in factori primi
while( Y>1 && pr[ind]<=lim ) {
int cnt= 0;
while( Y%pr[ind] == 0 ) {
++cnt;
Y/= pr[ind];
}
if( cnt ) {
p[ ++R ]= pr[ind];
lim= (int)sqrt(1.0*Y);
}
++ind;
}
if( Y>1 ) p[ ++R ]= Y;
/// PINEX :))
int sol= 0, k=(1<<R);
for( int i= 1; i<k; ++i ) {
int cnt= 0, prod= 1;
for( int j= 0; j<R; ++j ) {
if( i&(1<<j) ) {
++cnt;
prod*= p[j+1];
}
}
if( cnt%2 == 1 ) sol+= X/prod;
else sol-= X/prod;
}
/// Raspunsul
return X-sol;
}
int main() {
ciurul();
int rasp= 0;
int N,M;
in >> N >> M; --N; --M;
if( N > M ) swap(N,M);
for( int i= 1; i<=N; ++i ) {
rasp+= PINEX( M, i );
}
out << rasp << '\n';
return 0;
}