You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
26 lines
591 B
26 lines
591 B
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
typedef unsigned long long ULL;
|
|
const ULL mod = 1000000007;
|
|
|
|
ULL euler(ULL n) {
|
|
ULL res = n, a = n;
|
|
for (ULL i = 2; i * i <= a; i++) {
|
|
if (a % i == 0) {
|
|
res = res / i * (i - 1);
|
|
while (a % i == 0) a /= i;
|
|
}
|
|
}
|
|
if (a > 1) res = res / a * (a - 1);
|
|
return res;
|
|
}
|
|
|
|
int main() {
|
|
ULL n;
|
|
while (~scanf("%llu", &n), n) {
|
|
ULL sum = n * (1 + n) / 2 - n, ans;
|
|
ans = sum - euler(n) * n / 2;
|
|
printf("%llu\n", ans % mod);
|
|
}
|
|
return 0;
|
|
} |