Brian Warehouse

Some birds aren`t meant to be caged, their feathers are just too bright... ...
posts - 40, comments - 16, trackbacks - 0, articles - 1

SGU 107 987654321 problem

Posted on 2010-08-17 13:27 Brian 阅读(293) 评论(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理