D Farey Sequence Length Given a positive integer, N, the sequence of all fractions a / b with (0 < a b), (1 < b N) and a and b relatively PRime, listed in increasing order, is called the Farey Sequence of order N. For example, the Farey Sequence of order 6 is: 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1 For this problem, you will write a program to compute the length of the Farey sequence of order N (input). Input The first line of input contains a single integer P, (1 P 10000), which is the number of data sets that follow. Each data set should be processed identically and independently. Each data set consists of a single line of input. It contains the data set number, K, followed by the order N, N (2 <= N <= 10000), of the Farey Sequence whose length is to be found. Output For each data set there is a single line of output. The single output line consists of the data set number, K, followed by a single space followed by the length of the Farey Sequence as a decimal integer. Sample Input Sample Output 4 1 6 2 15 3 57 4 9999 1 13 2 73 3 1001 4 30393487
直接判断互质会超时，换个方式，只要和这个数有公约数就排除，一个数和本身肯定不互质（1除外），初始化dp[i] = i - 1，然后从1 ～ 10000遍历，依次查找 i 的约数a和，者大于等于 i + a的都和i不互质，最后 i 本身有可能是质数～～时间复杂度O（10^8）
AC代码：
#include<cstdio>#include<cstring>using namespace std;int dp[10010],vis[10010];int main(){ int T,K,N; scanf("%d",&T); for(int i = 1; i <= 10000; i++) dp[i] = i - 1;dp[1] = 2; for(int i = 2; i <= 10000; i++){ memset(vis,0,sizeof(vis)); for(int j = 2; j * j <= i; j++){ if(i % j == 0){ int p = i / j; for(int k = i + j; k <= 10000; k += j) if(!vis[k]) vis[k] = 1,dp[k]--; for(int k = i + p; k <= 10000; k += p) if(!vis[k]) vis[k] = 1,dp[k]--; } } for(int j = i + i; j <= 10000; j += i) if(!vis[j]) vis[j] = 1,dp[j]--; } int ans = 0; for(int i = 1 ; i <= 10000; i++) dp[i] += ans,ans = dp[i]; while(T--){ scanf("%d %d",&K,&N); printf("%d %d/n",K,dp[N]); } return 0;}新闻热点
疑难解答
