Posted on 2010-08-17 13:27
Brian 阅读(303)
评论(0) 编辑 收藏 引用 所属分类:
SGU
For given number N you must output amount of N-digit numbers, such, that last digits of their square is equal to 987654321.
Input
Input contains integer number N (1<=N<=106)
首先想到的是枚举，我确实也这么做了，5~8无果，对于9，我的05年方正 Pentium M 上跑了足足1分半钟之久，我一开始还以为死循环了，后来出来八个结果，也去网上核对了一下，确实满足的只有这八个:
111111111
119357639
380642361
388888889
611111111
619357639
880642361
888888889
我没有学过数论，找到一篇博文，对于数论解法讲的还算清楚，不过用pascal写就，我自己用C写了一下，第三次AC了。博文链接如下：http://blog.csdn.net/Skyprophet/archive/2009/10/05/4634801.aspx
#include <stdio.h>
int main()
{
int N,i=0;
scanf("%d",&N);
if (N<=8)
printf("0\n");
else if (N==9)
printf("8\n");
else
{
printf("72");
for (; i<N-10; i++)
printf("0");
printf("\n");
}
return 0;
}
336MS 0K