嗯，确实通过了！规律不好找啊！

偶写的东西就是考虑两数互为素数.
再由于对称性(互换性)即a和b互为素数,则b和a也互为素数.
所以a[i]+=2;而不是加1.
用到了一个递归求最大公约数的函数,应该比较好理解.返回1,则互为素数.
(0,1)(1,0)(1,1)三个点特殊考虑,所以从2开始做起.
先把1000项都写出来,再去找,避免重复用同样的事

能翻译一下原文吗
我不怎么懂啊

当规模为1000时,耗时0.01秒
即使把规模扩大10倍,即1 <= N <= 10000,也不会超时,耗时0.59秒

#include <stdio.h>
#define MAXSIZE 1000
#define DELETED 1
#define KEPT 0

void Sieve(int *prime) /*求MAXSIZE以内的素数,并存如数组prime中*/
{
int flag[MAXSIZE + 1];
int i, j, index = 0;

for (i = 2; i <= MAXSIZE; i++)
flag[i] = KEPT;
for (i = 2; i <= MAXSIZE; i++)
{
if (flag[i] == KEPT)
{
for (j = i + i; j <= MAXSIZE; j += i)
flag[j] = DELETED;
}
}
for (i = 2; i <= MAXSIZE; i++)
if (flag[i] == KEPT)
prime[index++] = i;
prime[index] = MAXSIZE + 1;
}

int increment(int n, int *prime) /*规模由n-1增大到n时,增加的点数*/
{
int i, j, flag[MAXSIZE + 1];
int count = n - 1;

for (i = 0; i <= MAXSIZE; i++)
flag[i] = KEPT;
for (i = 0; prime[i] <= n - 1; i++)
{
if (n % prime[i] == 0)
{
for (j = prime[i]; j <= n - 1; j += prime[i])
if (flag[j] == KEPT)
{
flag[j] = DELETED;
count--;
}
}
}
return count * 2;
}

int main()
{
int points[MAXSIZE + 1], prime[MAXSIZE];
int i, n, number;
int index = 1;

Sieve(prime);
points[1] = 3;
for (i = 2; i <=MAXSIZE; i++)
points[i] = points[i-1] + increment(i, prime);
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &number);
printf("%d %d %d\n", index, number, points[number]);
index++;
}
return 0;
}

[此贴子已经被作者于2006-12-10 15:14:34编辑过]

48K 0MS GCC 1561B
我试了一下！呵呵！通过了！上面是通过时的数据！

我的程序
#include<stdio.h>
int MGYS(int n1,int n2)
{int a,b,y;
a=n1>n2?n1:n2;
b=n1>n2?n2:n1;
y=a%b;
while(y>0)
{a=b;
b=y;
y=a%b;
}
return b;
}

main()
{long a[1002];
int i,j,n,N,t=0;
a[1]=0;
for(i=2;i<=1000;i++)
{ a[i]=a[i-1];
for(j=1;j<i;j++)
if(MGYS(i,j)==1) a[i]++;
}
scanf("%d",&N);
while(N--)
{
scanf("%d",&n);
printf("%d %d %ld\n",++t,n,(a[n]*2+3));
}
}