Question

一道小小的ACM题，用C或者C++写，提交老是说超时，求高人指点迷津

源码：#include "stdio.h"int main(){ int n,i = 0; scanf("%d",&n); while(n) { int j,a = 1; int t = n; for(j = 2;j < n;j++) if(t % j == 0) { t= t / j; a= a * (j - 1); } if(a == 1) a = t - 1; else a =a * t; printf("%d\n",a); scanf("%d",&n); } return 0;}原题：LK的数学题时间限制：1000 ms | 内存限制：65535 KB难度：3描述 LK最近遇到一个问题，需要你帮她一下。一个整数n，求[1,n)中，和n互素的数的个数。输入 多组测试数据，每一行有一个整数n（n<1000000001），0表示输入结束。输出 小于n同时和n互素的整数的个数样例输入 7 12 0样例输出 6 4

Answer 1

造成超时可能是因为你每次都是读取一个数然后输出一个结果。这可能和测试系统的输入输出连接矛盾。
试试找个数组将所有输入全部读进来，存放在里面，然后再一个一个计算输出。就是先统一输入，然后统一输出。

Answer 2

#include "stdio.h"
#include<math.h>
int main()
{
__int64 n,i = 0;
scanf("%I64dd",&n);
while(n)
{
__int64 j,a = 1;
__int64 t=n,m = (__int64)sqrt((double)n);
for(j = 2;j <= m;j++)
if(t % j == 0)
{
t= t / j;
a= a * (j - 1);
}
if(a == 1)
a = t - 1;
else
a =a * t;
printf("%I64d\n",a);
scanf("%I64d",&n);
}
return 0;
}
试试这个