Pagini recente » Cod sursa (job #3342835) | Cod sursa (job #1662720) | Cod sursa (job #3353029) | Cod sursa (job #3327433) | Cod sursa (job #3311284)
#include <fstream>
using namespace std;
const int Cmax = 1000005;
int c, d, ciur[Cmax], antiSol;
bool bad[Cmax];
int findCoef(int nr){
if(bad[nr]){
return 0;
}
if(ciur[nr] % 2 == 0){
return -1;
}
return 1;
}
int main(){
ifstream fin("mins.in");
ofstream fout("mins.out");
fin >> c >> d;
c--; d--;
// cautam perechile (x,y) cu 1 <= x <= c && 1 <= y <= d
// astfel incat cmmdc(x, y) >= 2
for(int i = 2; i <= min(c,d); i++){
ciur[i] = 1;
}
for(int i = 2; i * i <= min(c,d); i++){
if(ciur[i]){
for(int j = 2 * i; j <= min(c,d); j += i){
ciur[j]++;
}
for(int j = i * i; j <= min(c,d); j += i*i){
bad[j]=true;
}
}
}
for(int k = 2; k <= min(c,d); k++){
int aux = (c/k)*(d/k);
int coef = findCoef(k);
antiSol = antiSol + coef*aux;
}
fout << c*d - antiSol;
return 0;
}