Pagini recente » Cod sursa (job #429569) | Cod sursa (job #1402091) | Cod sursa (job #2018381) | Cod sursa (job #2685532) | Cod sursa (job #2636612)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
int l[1000001], w[1000001];
vector<int> prime;
int c, d;
void do_p() {
for (int i = 2; i <= 1000000; i++) {
if (l[i] == 0) {
l[i] = i;
prime.push_back(i);
w[i] = prime.size() - 1;
}
for (int j = w[l[i]]; j >= 0 && 1ll * i * prime[j] <= 1000000; j--) {
l[i * prime[j]] = prime[j];
}
}
}
bool coprime(int a, int b) {
if (a == 1 || b == 1)
return 1;
while (l[a] != l[b] && a > 1 && b > 1) {
if (l[a] > l[b])
b /= l[b];
else
a /= l[a];
}
if (l[a] == l[b])
return 0;
return 1;
}
int phi_p(int x) {
if (x <= d)
return x - 1;
return d;
}
int phi(int x) {
int p = 1;
while (x > 1) {
p *= phi_p(l[x]);
x /= l[x];
}
return p;
}
int phi_no_res(int x) {
int p = 1;
while (x > 1) {
p *= l[x] - 1;
x /= l[x];
}
return p;
}
int main() {
do_p();
int ans = 0;
in >> c >> d;
if (c < d)
swap(c, d);
for (int i = 1; i <= c - 1; i++) {
ans += phi(i);
}
for (int i = 1; i <= d - 1; i++) {
ans += phi_no_res(i);
}
out << ans;
return 0;
}