Posted on 2010-08-17 13:27
Brian 閱讀(321)
評論(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