Posted on 2010-08-17 13:27
Brian 閱讀(319)
評(píng)論(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)
首先想到的是枚舉，我確實(shí)也這么做了，5~8無(wú)果，對(duì)于9，我的05年方正 Pentium M 上跑了足足1分半鐘之久，我一開(kāi)始還以為死循環(huán)了，后來(lái)出來(lái)八個(gè)結(jié)果，也去網(wǎng)上核對(duì)了一下，確實(shí)滿足的只有這八個(gè):
111111111
119357639
380642361
388888889
611111111
619357639
880642361
888888889
我沒(méi)有學(xué)過(guò)數(shù)論，找到一篇博文，對(duì)于數(shù)論解法講的還算清楚，不過(guò)用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