Pagini recente » Cod sursa (job #64834) | Cod sursa (job #3332092) | Cod sursa (job #765095) | Monitorul de evaluare | Cod sursa (job #3311285)
#include <fstream>
using namespace std;
const int Cmax = 1000005;
int c, d, ciur[Cmax];
long long antiSol;
bool bad[Cmax];
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++){
long long aux = (c/k)*(d/k);
if(bad[k]){
continue;
}
if(ciur[k] % 2 == 1){
antiSol += aux;
}
else{
antiSol -= aux;
}
}
fout << c*d - antiSol;
return 0;
}