给出一个Answer(x,y)函数，x,y属于[1,N]，$Answer(k_x, k_y)$可以由Answer(x,y)得出，目的是求需要计算多少Answer(x,y)。
就是求1,N范围的欧拉函数的加和。欧拉函数的定义是与N互质的数的个数，所以需要如此计算。一开始没有发现就是求欧拉惭愧惭愧。
#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数，内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++) const double PI = acos(-1.0); #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << " "; } cout << endl; } const int maxn = 1e5 + 10; int phi[maxn]; void phi_table(int n) { memset(phi, , sizeof(phi)); phi[1] = 1; for(int i = 2; i <= n; i++) if(!phi[i]) for(int j = i; j <= n;j += i) { if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i-1); } } int main() { #ifdef DEBUG // freopen("input", "r", stdin); //从input文件中读入 // freopen("output", "w", stdout); //输出到output文件 #endif int N; phi_table(maxn-1); ll ans; while(scanf("%d", &N), N) { ans =; for(int i = 1; i <= N;i ++) ans += phi[i]; ans = ans *2 - 1; printf("%lld\n", ans); } return ; }