学步园

题目：

E(N) = |{i | gcd(N, i) = 1, 1 <= i <= N}|
F(N) = |{i | N % i = 0, 1 <= i <= N}|

求有多少区间段[l,r]（1<=l<=r<=n）,满足上式，输出，

打表后，发现29以后都是10  ^-^

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int answer[31]={0,1,1,2,2,4,5,5,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,10};
	int n,c;
	scanf("%d",&c);
	for(int t=1;t<=c;t++)
	{
		scanf("%d",&n);
		if(n<30)
			printf("Case %d: %d\n",t,answer[n]);
		else
			printf("Case %d: 10\n",t);
	}
	system("pasue");
    return 0;
}

打表程序：

#include<iostream>
#include<cstdio>
using namespace std;
int  gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y);
}
int E[10000],F[10000];
int answer[10000];
int main()
{
   int n;
   while(scanf("%d",&n)!=EOF)
   {
	    memset(E,0,sizeof(E));
	    memset(F,0,sizeof(F));
        for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
			{
               if(gcd(i,j)==1)
				   E[i]++;
			   if(i%j==0)
				   F[i]++;
			}
		}
		for(int i=1;i<=1000;i++)
		{
		    printf("%d ",E[i]);
			if(i%20==0)
				printf("\n");
		}
		cout<<"******************************************************************"<<endl;
		for(int i=1;i<=1000;i++)
		{
			printf("%d ",F[i]);
			if(i%20==0)
				printf("\n");	
		}
		cout<<"*******************************************************************"<<endl;
		
		for(int t=1;t<=200;t++)
		{
		    int sumE,sumF,ans=0;
	        for(int i=1;i<=t;i++)
		    {
				 /* sumE=0;//重算了
			     sumF=0;*/
			     for(int j=1;j<=i;j++)
			     {
				   /*sumE+=E[j];
				sumF+=F[j];
				if(j==2)
				{
					printf("sunE=%d***sumF=%d\n\n",sumE,sumF);
				}
				if(sumE==sumF)
				{
					printf("sumE=%d   sumF=%d\n",sumE,sumF);
					printf("j=%d   i=%d\n",j,i);
				    ans++;
				}*/
				    sumE=0;
			        sumF=0;
				    for(int k=j;k<=i;k++)
				    {
                       sumE+=E[k];
			           sumF+=F[k];
			            /*if(sumE==sumF)//放错位置了！！！！！
					{
						printf("sumE=%d   sumF=%d\n",sumE,sumF);
						printf("j=%d   i=%d\n",j,i);
				       ans++;
					}*/
				    }
	                if(sumE==sumF)
			        {
				        /*printf("sumE=%d   sumF=%d\n",sumE,sumF);
					     printf("j=%d   i=%d\n",j,i);*/
				         ans++;
				     }
			     }
		     }
		     //printf("%d***\n",ans);
	     answer[t]=ans;
		}
		for(int i=1;i<=200;i++)
		{
			printf("%d  ",answer[i]);
			if(i%10==0)
				printf("\n");
		}
   }
   system("pause");
   return 0;
}

n取值为前100时，

1  1  2  2  4  5  5  6  6  7
7  7  7  7  7  7  7  8  8  8
8  8  8  9  9  9  9  9  9  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10  10  10