GDUT1141：求互质对数（递推 ）

1141: 求互质对数

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 2239   Solved: 358

Description

 1到n中，任意选择两个数，使其互质，问总共有多少种选择方法，注意（1，2）和（2，1）是同一种方案

Input

输入有多组数据，第一行输入T（T<=100000）

接下来每一行输入一个n，(1<=n<=1000)

Output

 每一行输出一个方案数

Sample Input

12

Sample Output

1

HINT

Source

思路：欧拉函数表 + 递推打表，或者不用欧拉直接递推也可以。

# include <stdio.h> # define MAXN 1000 # define LL long long LL phi[MAXN<<1], ans[MAXN+3]={0}; void phi_table(int n) { for(int i=2; i<=n; ++i) phi[i] = 0; 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() { int n, t; scanf("%d",&t); phi_table(MAXN); for(int i=2; i<=MAXN; ++i) ans[i] = phi[i] + ans[i-1]; ans[1] = 0; while(t--) { scanf("%d",&n); printf("%lld\n",ans[n]); } return 0; }