Pagini recente » Cod sursa (job #673562) | Cod sursa (job #2282887) | Cod sursa (job #1742253) | Cod sursa (job #3167906) | Cod sursa (job #2883622)
#include <bits/stdc++.h>
using namespace std;
const int VALMAX = 1e6;
int nrdiv[VALMAX + 1];
int prime[VALMAX];
int main() {
int n, x, y, nrprime;
FILE *fin, *fout;
fin = fopen("mins.in", "r");
fscanf(fin, "%d%d", &x, &y);
fclose(fin);
n = min(x - 1, y - 1);
nrprime = 0;
for(int i = 2; i <= n; i++) {
if(nrdiv[i] == 0) {
prime[nrprime++] = i;
for(int d = i; d <= n; d += i)
nrdiv[d]++;
}
}
int i = 0;
while(i < nrprime && prime[i] * prime[i] <= n) {
for(int d = prime[i] * prime[i]; d <= n; d += prime[i] * prime[i])
nrdiv[d] = -1;
i++;
}
long long ans = 1LL * (x - 1) * (y - 1);
for(int i = 2; i <= n; i++) {
if(nrdiv[i] != -1) {
if(nrdiv[i] % 2 == 0)
ans += (1LL * (x - 1) / i) * (1LL * (y - 1) / i);
else
ans -= (1LL * (x - 1) / i) * (1LL * (y - 1) / i);
}
}
fout = fopen("mins.out", "w");
fprintf(fout, "%lld", ans);
fclose(fout);
return 0;
}