题解

40 条题解

  • 1
    @ 2009-10-29 17:00:47

    除了1以外,所有数的阶乘的最右非零位都是2,4,6,8中的一个。而6乘以这四个数当中的任意一个位数都不变。因为产生零的原因是因为有成对的2和5,所以考虑一个只含一个质因子2和和一个质因子5的数x = k*10 , x的尾数与y = k*16的尾数数是相同的,所以把10换成了16,既是把5换成了8:f(x) = f(k*2*5) = f(k*2*8)。

    8的次幂的尾数的循环节是4,而1到10当中除去5和10后的数有1,2,3,4,6,7,8,9,这几个数也可以构成尾数循环。

    这样算法就出炉了:每次把凡是是5的倍数的都不管,先算所有尾数1,2,3,4,6,7,8,9乘起来的尾数k1,然后求出五的倍数的数的个数,就是1*5,2*5,3*5,4*5,5*5,6*5...把里面的五全换成8,求8的次幂的尾数k2,然后剩下的又是一轮新的1,2,3,4,5,6...递归处理就行了。

    #include

    #define ll long long

    using namespace std;

    ll g101[] = {1,1,2,6,4,2,2,4,2,8,8};

    ll g102[] = {6,1,2,6,4,4,4,8,4,6};

    ll g8[] = {6,8,4,2};

    ll dfs(ll n){

    if (n

  • 0
    @ 2012-11-04 12:56:22

    蛋疼。。。

    const

    d1:array[0..10] of integer=(1,1,2,6,4,2,2,4,2,8,8);

    d2:array[0..9] of integer=(6,1,2,6,4,4,4,8,4,6);

    d3:array[0..3] of integer=(6,8,4,2);

    var

    n:qword;

    function work(n:qword):longint;

    begin

    if n

  • 0
    @ 2012-11-04 12:30:02

    ├ 测试数据 01:答案正确... (0ms, 408KB)

    ├ 测试数据 02:答案正确... (0ms, 408KB)

    ├ 测试数据 03:答案正确... (0ms, 404KB)

    ├ 测试数据 04:答案正确... (0ms, 408KB)

    ├ 测试数据 05:答案正确... (0ms, 408KB)

    ├ 测试数据 06:答案正确... (0ms, 408KB)

    ├ 测试数据 07:答案正确... (0ms, 408KB)

    ├ 测试数据 08:答案正确... (0ms, 408KB)

    ├ 测试数据 09:答案正确... (0ms, 408KB)

    ├ 测试数据 10:答案正确... (0ms, 408KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 0ms / 408KB

    规模10^18,用数级递推式AC

    {

    ID:darkgod-z

    PROG:vijos P1669

    HANG:PASCAL

    }

    const

    t:array [0..9] of integer=(1,1,2,6,4,2,2,4,2,8);

    var

    n:string;

    function f(n:string):integer;

    var

    ff,g,i:integer;

    begin

    ff:=1;

    while length(n)>1 do begin

    ff:=ff*t[ord(n[length(n)])-48];

    if odd(ord(n[length(n)-1])) then g:=4

    else g:=6;

    ff:=(ff*g) mod 10;

    if n[1]>='5' then n:='0'+n;

    for i:=1 to length(n)-1 do

    n[i]:=chr(( ( (ord(n[i])-48) shl 1) mod 10)+ord(n>='5')+48);

    delete(n,length(n),1);

    end;

    f:=(t[ord(n[1])-ord('0')]*ff) mod 10;

    end;

    begin

    readln(n);

    writeln(f(n));

    end.

  • 0
    @ 2009-11-10 17:59:53

    这题就是1505的一部分。。

  • 0
    @ 2009-11-05 21:54:23

    const maxn=50;

    type ar=array[0..maxn]of longint;

    var i,j,k,l:longint;

    st:string;

    ff:array[0..200]of longint;

    s,r:ar;

    function divi(a:ar;b:longint):ar;

    var i,k,sum:longint;

    begin

    fillchar(divi,sizeof(divi),0);

    for i:=maxn downto 1 do if a[i]>0 then begin k:=i; break; end;

    sum:=0;

    for i:=k downto 1 do begin

    inc(sum,a[i]);

    if sum>=b then divi[i]:=sum div b;

    sum:=sum mod b;

    sum:=sum*10;

    end;

    end;

    function fact(a:ar):boolean;

    var i,j:longint;

    begin

    fact:=false;

    for i:=2 to maxn do if a[i]>0 then fact:=true;

    end;

    function find(a:ar):longint;

    var ll,u,fn:longint;

    begin

    if not(fact(a)) then find:=ff[a[1]]

    else begin

    if a[2] mod 2=1 then u:=4 else u:=1;

    fn:=ff[a[1]];

    ll:=find(divi(a,5));

    find:=ll*u*fn mod 10;

    end;

    end;

    begin

    readln(st);

    l:=length(st);

    fillchar(s,sizeof(s),0);

    for i:=1 to l do s[i]:=ord(st[l+1-i])-48;

    fillchar(r,sizeof(r),0);

    ff[0]:=1; ff[1]:=1; ff[2]:=2; ff[3]:=6; ff[4]:=4;

    ff[5]:=2;ff[6]:=2;ff[7]:=4;ff[8]:=2;ff[9]:=8;

    writeln(find(s));

    end.

  • 0
    @ 2009-10-28 16:45:07

    直接拿前面的某某原题来交....忘了编号是多少了.....

    瀑布飞汗...........

    ---|---|---|---|---|---|---|---|---|

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-28 16:42:09

    只是不想写高精度,干嘛非要让我的int64WA3次??

    算了,不计较这些了,高精就高精嘛。

    我写的不是题,是代码.....

    我汗....

    ---|---|---|---|---|---|---|---|---|---|-

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-26 16:19:53

    随机得70。。胡扯

    交了两次,一次40,一次30

  • 0
    @ 2009-10-19 19:32:20

    我果然只是beginer,数论爽到暴,最后还是不行

  • 0
    @ 2009-10-21 17:32:11

    orz qiao

  • 0
    @ 2009-10-18 16:55:40

    随机得70

    program jc;

    var i:longint;

    s,n:qword;

    begin

    s:=1;

    readln(n);

    if n

  • 0
    @ 2009-10-17 11:55:57

    公式f(n)=f([n/5])*4^([n/10] mod 2)*f(n mod 10) mod 10

  • 0
    @ 2009-10-15 08:09:13

    50人留念- -

  • 0
    @ 2009-10-14 22:28:28

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    额额..

    数学方法就是好..

    Orz YZT大牛..

  • 0
    @ 2009-10-14 20:32:56

    编译通过...

    ├ 测试数据 01:答案错误...

     ├ Hint: 这个是最小的点. ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 02:答案错误...

     ├ Hint: 这个点很寂寞.也是最大的点. ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误...

     ├ Hint: 这个点的数据很寂寞很有爱 ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 05:答案错误...

     ├ Hint: 知道么我做这个数据的时候肚子很饿 ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 06:答案错误...

     ├ Hint: 知道么我做这个数据的时候很想要个GF. ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 07:答案错误...

     ├ Hint: 知道么我做这个数据的时候很希望我能一等 ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 08:答案错误...

     ├ Hint: 知道么我做这个数据的时候很希望我能在各种OI赛场上驰骋 ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案错误...

     ├ Hint: 知道么其实这个数据分布是逆序的 ├ 标准行输出

     ├ 错误行输出

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:20 有效耗时:0ms

    var

    n:Qword;

    s:longint;

    r,i:0..9;

    begin

    readln(n);

    r:=n mod 10;s:=1;

    for i:=2 to r do

    begin

    s:=s*i;

    while s mod 10=0 do s:=s div 10;

    end;

    s:=s*6;

    s:=s mod 10;

    writeln(s);

    end.

    Flag    Unaccepted

    题号   P1669

    类型(?)   数论 / 数值

    通过   46人

    提交   255次

    通过率   18%

    难度   2

    怎么会这样?各位大牛!!!

  • 0
    @ 2009-10-14 16:12:32

    MS与1505重题,但是1505的数据显然大得多,过那题的程序肯定过这题,可是过这题的程序不一定过那题。

  • 0
    @ 2009-10-14 12:09:11

    出题人不是fjxmlhx,是寂寞......

  • 0
    @ 2009-10-14 00:32:43

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    经本班同学的提示 1*2*3*4*6*7*8*9的末尾是6 而6是个好东西

  • 0
    @ 2009-10-13 20:12:29

    水题

    害我想半天

    不断的去除5,然后统计一下0~9中每个数字在某尾出现的次数,最后按照每个数的循环节求解就行

    时间O(log5 N)

    另外膜拜one1one0 没看懂...

  • 0
    @ 2009-10-13 19:44:21

    usaco原题?

    shit.我说呢.把一个unsigned long long用"%d"去scanf…………………………………………

信息

ID
1669
难度
7
分类
其他 | 数学 点击显示
标签
递交数
772
已通过
174
通过率
23%
上传者