被机房oierA穿的一道题……
我最后还是靠着打表想出来了
其实就先沿着对角线分开 看一半
然后发现没有被覆盖的点纵坐标都是横坐标的因数
所以被覆盖的点就是欧拉函数
预处理一下前缀和 O(1000)
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<vector> 7 #define ms(a,b) memset(a,b,sizeof a) 8 #define rep(i,a,n) for(int i = a;i <= n;i++) 9 #define per(i,n,a) for(int i = n;i >= a;i--) 10 #define inf 2147483647 11 using namespace std; 12 typedef long long ll; 13 ll read() { 14 ll as = 0,fu = 1; 15 char c = getchar(); 16 while(c < '0' || c > '9') { 17 if(c == '-') fu = -1; 18 c = getchar(); 19 } 20 while(c >= '0' && c <= '9') { 21 as = as * 10 + c - '0'; 22 c = getchar(); 23 } 24 return as * fu; 25 } 26 const int N = 1005; 27 //head 28 int c; 29 int n; 30 int mindiv[N],prim[N],phi[N]; 31 int sig[N]; 32 void initphi(int n) { 33 phi[0] = phi[1] = 1; 34 mindiv[0] = mindiv[1] = 1; 35 rep(i,2,n) { 36 if(!mindiv[i]) prim[++prim[0]] = i,phi[i] = i-1; 37 for(int j = 1;j <= prim[0] && i * prim[j] <= n;j++) { 38 mindiv[i * prim[j]] = prim[j]; 39 if(i % prim[j] == 0) phi[i * prim[j]] = phi[i] * prim[j]; 40 else phi[i * prim[j]] = phi[i] * (prim[j]-1); 41 } 42 } 43 } 44 45 int main() { 46 initphi(1001); 47 rep(i,1,1000) sig[i] = sig[i-1] + phi[i]; 48 int T = read(); 49 rep(i,1,T) { 50 int n = read(); 51 printf("%d %d %d ",i,n,(sig[n]<<1)+1); 52 } 53 return 0; 54 }