/ Vijos / 题库 / 循环 /

题解

104 条题解

  • 4
    @ 2017-08-07 21:27:53

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    struct hp

    {
    int s[210];
    } n,a,b,ans;
    char N[110];
    int k,now,tmp;

    void mult1(hp a,hp b,hp &c,int d)
    {
    hp s;
    memset(s.s,0,sizeof(s.s));
    for(int i=1;i<=d;i++)
    for(int j=1;j<=d;j++)
    s.s[i+j-1]+=a.s[i]*b.s[j];
    for(int i=1;i<=d+1;i++)
    if (s.s[i]>=10)
    {
    s.s[i+1]+=s.s[i]/10;
    s.s[i]%=10;
    }
    c=s;
    }

    void mult2(hp a,int b,hp &c)
    {
    hp s;
    memset(s.s,0,sizeof(s.s));
    for(int i=1;i<=200;i++)
    s.s[i]+=a.s[i]*b;
    for(int i=1;i<=200;i++)
    if (s.s[i]>=10)
    {
    s.s[i+1]+=s.s[i]/10;
    s.s[i]%=10;
    }
    c=s;
    }

    int main()
    {
    scanf("%s %d",N,&k);
    for(int i=strlen(N)-1,j=1;i>=0;i--,j++)
    n.s[j]=N[i]-'0';
    ans.s[1]=1;
    a=n;
    for(now=1;now<=k;now++)
    {
    b=n;
    tmp=b.s[now];
    int len=0;
    do
    {
    mult1(a,b,b,k);
    len++;
    }while(len<10&&b.s[now]!=tmp);
    if (b.s[now]!=tmp)

    {
    printf("-1");
    return 0;
    }
    b=a;
    for(int i=1;i<=len-1;i++)

    mult1(a,b,a,k);
    mult2(ans,len,ans);
    }

    int out;
    for(out=200;ans.s[out]==0;out--);
    for(;out>=1;out--)
    printf("%d",ans.s[out]);
    return 0;
    }

  • 2
    @ 2014-12-23 15:36:34

    type use=array[1..1000] of integer;var n:string;
    meen,realk:integer;
    num1,ans,need:use;
    procedure init;
    var inite,k:string;
    space,error,for1:integer;
    begin readln(inite);
    space:=pos(' ',inite);
    n:=copy(inite,1,space-1);
    k:=inite; delete(k,1,space);
    val(k,realk,error);
    if length(n)>=for1 then delete(n,1,length(n)-realk);
    for for1:=realk downto 1 do if length(n)>=for1
    then num1[realk-for1+1]:=ord(n[for1])-48 else num1[realk-for1+1]:=0;
    end;
    procedure mult(var a:use;b:use;k1,k2:integer);
    var for1,for2,x,y,m:integer;

    c:array[1..100] of integer;
    begin
    fillchar(c,Sizeof(c),0);
    if k1>k2 then m:=k1 else m:=k2;
    for for1:=1 to k1 do for for2:=1 to k2 do
    begin

    x:=a[for1]*b[for2];
    y:=c[for1+for2-1];
    if for1+for2-1<=m then c[for1+for2-1]:=(x+y) mod 10;
    if for1+for2<=m then c[for1+for2]:=c[for1+for2]+(x+y) div 10;
    end;
    for for1:=1 to m do a[for1]:=c[for1];
    end;
    procedure TheWrongWay;
    begin
    writeln(-1);
    readln;
    halt;
    end;
    procedure working;
    var for1,for2,for3,box,new:integer;

    num2,num3,rp:use;

    find:array[0..9] of boolean;

    Yes:boolean;
    begin

    fillchar(need,Sizeof(need),0);
    for for1:=1 to realk do
    begin

    if for1=1 then
    begin
    ans[1]:=1;
    new:=1;
    fillchar(num3,Sizeof(num3),0);
    for for2:=1 to realk do num3[for2]:=num1[for2];
    end;
    fillchar(num2,Sizeof(num2),0);
    for for2:=1 to realk do num2[for2]:=num3[for2];
    if for1>1 then for for2:=1 to (need[for1-1])-1 do
    mult(num3,num2,realk,realk);
    for for2:=1 to for1 do
    num2[for2]:=num1[for2];

    new:=0;
    fillchar(find,Sizeof(find),false);
    box:=num2[for1];
    find[box]:=true;Yes:=false;
    repeat inc(new);

    mult(num2,num3,for1,for1);
    if not find[num2[for1]] then find[num2[for1]]:=true
    else
    begin

    if num2[for1]<>box then TheWrongWay
    else Yes:=true;
    end;

    until Yes;

    need[for1]:=new;
    fillchar(rp,Sizeof(rp),0);

    if new=10 then
    begin
    rp[2]:=1;

    rp[1]:=0;

    end
    else rp[1]:=new;
    mult(ans,rp,100,2);
    end;
    end;
    procedure print;
    var for1,for2:integer; begin for1:=100;

    while ans[for1]=0 do dec(for1);

    for for2:=for1 downto 1 do write(ans[for2]);

    writeln;
    readln;
    end;
    begin
    init;
    working;
    print;
    end.

  • 2
    @ 2009-11-04 18:31:21

    各位注意,答案是高精,太阴了!

    害我交了两次....

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

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    type

    arra=record

    da:array[0..210]of longint;

    l:longint;

    end;

    var

    k:longint;n,r:arra;

    function min(a,b:longint):longint;

    begin

    if alength(s1) then q:=length(s1) else q:=k;

    for i:=1 to q do

    begin

    n.da[i]:=ord(s1[length(s1)-i+1])-ord('0');

    end;

    n.l:=k;

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

    for i:=1 to n.l do r.da[i]:=n.da[i];

    r.l:=k;

    while (r.da[r.l]=0)and(r.l>1) do dec(r.l);

    end;

    function check(a,r:arra;k:longint):boolean;

    var

    i:longint;

    begin

    for i:=1 to k do

    begin

    if a.da[i]r.da[i] then exit(false);

    end;

    exit(true);

    end;

    procedure mult(a,b:arra;var r:arra);

    var

    i,j:longint;c:arra;

    begin

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

    fillchar(c,sizeof(c),0);

    for i:=1 to min(a.l,k) do

    for j:=1 to min(b.l,k) do

    begin

    c.da:=a.da[i]*b.da[j]+c.da;

    if c.da>=10 then

    begin

    c.da:=(c.da div 10)+c.da;

    c.da:=c.da mod 10;

    end;

    end;

    for i:=1 to k do r.da[i]:=c.da[i];

    r.l:=k;

    end;

    procedure accmult(a:arra;b:longint;var c:arra);

    var

    i:longint;

    begin

    fillchar(c,sizeof(c),0);

    c.l:=a.l+2;

    for i:=1 to c.l do

    begin

    c.da[i]:=a.da[i]*b+c.da[i];

    if c.da[i]>=10 then

    begin

    c.da:=(c.da[i] div 10)+c.da;

    c.da[i]:=c.da[i] mod 10;

    end;

    end;

    while (c.da[c.l]=0)and(c.l>1) do dec(c.l);

    end;

    procedure find;

    var

    i,j,times:longint;b:boolean;c,m,d,z:arra;

    begin

    fillchar(c,sizeof(c),0);

    m:=n;

    c.l:=k;

    fillchar(z,sizeof(z),0);

    z.l:=1;z.da[1]:=1;

    if (r.l=1)and(r.da[1]=0) then

    begin

    writeln(1);

    halt;

    end

    else

    for i:=1 to k do

    begin

    times:=1;

    repeat

    c:=r;

    mult(r,n,r);

    mult(c,m,d);

    inc(times);

    b:=check(m,d,i);

    until (b)or(times>10);

    if b then

    begin

    accmult(z,times-1,z);

    n:=c;

    r:=c;

    n.l:=k;

    end

    else

    begin

    writeln(-1);

    halt;

    end;

    end;

    for i:=z.l downto 1 do write(z.da[i]);

    end;

    begin

    init;

    find;

    end.

  • 1
    @ 2021-08-28 12:11:23
    #include<bits/stdc++.h>
    using namespace std;
    
    int xh[11]={1,1,4,4,2,1,1,4,4,2};
    int k,b[205],c[205],d[205],p[205],q[205],ss[205],tot1,tot2=2,t;
    char a[105];
    void mul1(int x[],int y[],int z[])
    {
        for(int i=1; i<=k; i++)
            for(int j=1; j<=k; j++){
                z[i+j-1]+=x[i]*y[j];
                z[i+j]+=z[i+j-1]/10;
                z[i+j-1]%=10;
            }
    }
    
    void mul2(int x[],int y,int z[])
    {
        for(int i=1; i<=k; i++){
            z[i]+=x[i]*y;
            z[i+1]+=z[i]/10;
            z[i]%=10;
        }
    }
    
    int main()
    {
        
        scanf("%s%d",a+1,&k);
        int len=strlen(a+1);
        for(int i=len; i>=len-k+1; i--)
            c[++tot1]=a[i]-'0';
        for(int i=1; i<=k; i++)
            b[i]=c[i];
        for(int i=1; i<xh[c[1]]; i++)
        {
            memset(d,0,sizeof(d));
            mul1(b,c,d);
            for(int j=1; j<=k; j++)
                b[j]=d[j];
        }
        ss[1]=xh[c[1]];
        for(int i=1; i<=k; i++)
            q[i]=p[i]=b[i];
        while(tot2<=k)
        {
            for(int i=1; i<=k; i++)
                b[i]=c[i];
            while(t<11)
            {
                memset(d,0,sizeof(d));
                mul1(b,p,d);
                t++;
                for(int i=1; i<=k; i++)
                    b[i]=d[i];
                if(b[tot2]==c[tot2])
                    break;
                memset(d,0,sizeof(d));
                mul1(q,p,d);
                for(int i=1; i<=k; i++)
                    q[i]=d[i];
            }
            if(t==11){
                cout<<-1;
                return 0;
            } 
            for(int i=1; i<=k; i++)
                p[i]=q[i];
            memset(d,0,sizeof(d));
            mul2(ss,t,d);
            for(int i=1; i<=100; i++)
                ss[i]=d[i];
            tot2++;t=0;
        }
        int len1=105;
        while(ss[len1]==0 && len1>1)
            len1--;
        for(int i=len1; i>=1; i--)
            cout<<ss[i];
        return 0;
    }
    
  • 1
    @ 2019-07-17 18:40:09

    状态 耗时 内存占用

    #1 Accepted 1ms 212.0 KiB
    #2 Accepted 1ms 228.0 KiB
    #3 Accepted 1ms 220.0 KiB
    #4 Accepted 1ms 228.0 KiB
    #5 Accepted 1ms 224.0 KiB
    #6 Accepted 1ms 232.0 KiB
    #7 Accepted 1ms 228.0 KiB
    #8 Accepted 1ms 228.0 KiB
    #9 Accepted 1ms 224.0 KiB
    #10 Accepted 1ms 228.0 KiB

    没想到速度这么快?!就跟直接打数据一般。

    想清楚几点就简单了。
    1.循环是从1开始,找到下一个与第一个位置相同的地方就算成功了。(之前做成了,从中途某一个地方开始之后发生循环。然后有个数据会被找到循环数)
    2.虽然是找末K位,但是显然的,只要末K位的产生了循环,其末K-1位一定也是循环。反之也即是,K-1位达成了循环后(假设循环次数为N),那么如果有循环产生,那么循环一定是N的倍数。因此算法可以用类似数学归纳法的方式来进行求解。
    3.答案很大,要高精。
    4.速度快可能是因为用的指针的关系?

    PS.终于报了当年的一箭之仇,没错,这是我那年的考题。。。

  • 1
    @ 2017-03-18 14:37:59

    高精度的题目为什么不用python?

    n , k = [int(i) for i in raw_input().split()]
    ans = 1
    mod = 1
    m = 10 ** k
    flag = True
    for i in range(k):
        mod *= 10
        t = ans
        a = n
        while (n * a % mod) != (a % mod):
            ans += t
            n = n * a % m
            if ans > t * 10:
                print("-1")
                flag = False
                break
        if not flag:
            break
    if flag:
        print(ans)
    
  • 1
    @ 2014-10-18 21:51:52

    ###Block Code
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    int n, k, ans[110];
    struct Num {
    int len, a[110];
    Num() {
    this->len = 1;
    memset(this->a, 0, sizeof(this->a));
    }
    int& operator {
    return this->a[i];
    }
    };
    void copyNum(Num& a, Num b, int k = -1) {
    int i;
    k = (k == -1) ? b.len : k;
    a.len = std::min(b.len, k);
    memset(a.a, 0, sizeof(a.a));
    for(i = 1; i <= k; i++) {
    a[i] = b[i];
    }
    }
    void setString(Num& a, const char * str, int k = -1) {
    int i, n = strlen(str);
    k = (k == -1) ? n : k;
    memset(a.a, 0, sizeof(a.a));
    for(i = 1; i <= n && i <= k; i++) {
    a[i] = str[n - i] - '0';
    }
    a.len = k;
    }
    Num multiK(Num a, Num b, int k) {
    int i, j, ij;
    Num c;
    for(i = 1; i <= k; i++) {
    for(j = 1; i + j - 1 <= k; j++) {
    ij = i + j - 1;
    c[ij] += a[i] * b[j];
    if(c[ij] > 9) {
    if(ij < k) {
    c[ij + 1] += c[ij] / 10;
    }
    c[ij] %= 10;
    }
    }
    }
    c.len = k;
    while(c[c.len] == 0) {
    c.len--;
    }
    return c;
    }
    Num multi(Num a, int b) {
    int i, x = 0;
    Num c;
    copyNum(c, a);
    for(i = 1; i <= c.len; i++) {
    c[i] = c[i] * b + x;
    x = c[i] / 10;
    c[i] %= 10;
    if(i == c.len && x > 0) {
    c.len++;
    }
    }
    return c;
    }
    int main() {
    int k, i, j, tmp;
    char str[110];
    Num x, y, xx, result;
    scanf("%s%d", str, &k);
    setString(x, str, k);
    setString(result, "1");
    copyNum(xx, x, k);
    for(i = 1; i <= k; i++) {
    copyNum(y, xx, i);
    j = y[i];
    tmp = 0;
    do {
    copyNum(y, multiK(y, x, i), k);
    tmp++;
    } while(tmp < 10 && y[i] != j);
    if(j != y[i]) {
    printf("-1\n");
    return 0;
    }
    copyNum(y, x, k);
    for(j = 1; j < tmp; j++) {
    copyNum(x, multiK(x, y, k));
    }
    copyNum(result, multi(result, tmp));
    }
    for(i = result.len; i >= 1; i--) {
    printf("%d", result[i]);
    }
    printf("\n");
    return 0;
    }
    cpp版调试N+1次在Codevs上过了来Vijos再测测
    强烈鄙视楼上打表

  • 1
    @ 2013-12-11 21:34:17

    曾经n次想过此题,但都是wa了
    在本地写过n次,调了n次
    最后终于

    __测试数据 0: Accepted, time = 0 ms, mem = 440 KiB, score = 10

    __测试数据 1: Accepted, time = 0 ms, mem = 436 KiB, score = 10

    __测试数据 2: Accepted, time = 0 ms, mem = 436 KiB, score = 10

    __测试数据 3: Accepted, time = 62 ms, mem = 440 KiB, score = 10

    __测试数据 4: Accepted, time = 0 ms, mem = 444 KiB, score = 10

    __测试数据 5: Accepted, time = 62 ms, mem = 432 KiB, score = 10

    __测试数据 6: Accepted, time = 62 ms, mem = 440 KiB, score = 10

    __测试数据 7: Accepted, time = 46 ms, mem = 444 KiB, score = 10

    __测试数据 8: Accepted, time = 78 ms, mem = 436 KiB, score = 10

    __测试数据 9: Accepted, time = 93 ms, mem = 436 KiB, score = 10

    细节永远是重要的。
    #code:
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    typedef char big[105];
    big now,now2,now3,time,ans,ans2,now4;/*now2:now3*now,
    now3:time^now4*/
    int l;
    void smlt1(char *a,char *b,char *c)
    {
    int static i;
    void smlt2(char *a,int b,char *c,int num);
    memset(c,'0',sizeof(char)*104); (c+104) = 0;
    for (i = 0;
    (b+i) && i < 105;i++)
    smlt2(a,(*(b+i))-'0',c+i,i);
    *(c+104) = 0;
    }
    void smlt2(char *a,int b,char *c,int num)
    {
    int static tmp1,tmp2;
    tmp1 = tmp2 = 0;
    while ((*a) && (num < l)) {
    tmp1 = (*a)-'0';
    tmp2 += tmp1*b;
    if (*c) {
    tmp2 = tmp2-'0'+*c;
    *c = '0'+tmp2%10;
    } else {
    *c = '0'+tmp2%10;
    }
    tmp2 /= 10;
    a++,c++;
    num++;
    }
    while ((tmp2) && (num < l)) {
    if (*c) {
    tmp2 = tmp2-'0'+*c;
    *c = '0'+tmp2%10;
    } else {
    *c = '0'+tmp2%10;
    }
    tmp2 /= 10;
    c++;
    num++;
    }
    }
    int check(int k)
    {
    smlt1(now4,time,now3);
    strcpy(now4,now3);
    smlt1(now3,now,now2);
    if (now[k] == now2[k])
    return 1;
    else
    return 0;
    }

    void print_big(char *s)
    {
    char *p;
    p = strlen(s)+s-1;
    while (p > s) {
    if ((*p) != '0')
    break;
    p--;
    }
    while (p >= s) {
    printf("%c",*p);
    p--;
    }
    printf("\n");
    }

    void clear1(char *s)
    {
    memset(s,0,sizeof(char)*105);
    *s = '1';
    }

    int main()
    {
    int i,j;

    void init();

    init();
    for (i = 0;i < l;i++) {
    strcpy(time,now3);
    clear1(now4);
    for (j = 1;j <= 10;j++)
    if (check(i) == 1)
    break;
    if (j != 11) {
    memset(ans2,0,sizeof(char)*105);
    smlt2(ans,j,ans2,0);
    strcpy(ans,ans2);
    if (i == l-1)
    break;
    } else {
    printf("-1\n");
    return 0;
    }
    }
    print_big(ans);
    return 0;
    }

    void reverse(char *s)
    {
    char *p,ch;
    p = strlen(s)+s-1;
    while (p > s) {
    ch = *p; *p = *s; *s = ch;
    p--; s++;
    }
    }

    void init()
    {
    memset(now2,0,sizeof(char)*105);
    memset(now3,0,sizeof(char)*105);
    memset(time,0,sizeof(char)*105);
    memset(ans,0,sizeof(char)*105);
    memset(ans2,0,sizeof(char)*105);
    memset(now4,0,sizeof(char)*105);
    scanf("%s",now);
    reverse(now);
    strcpy(now3,now); strcpy(now2,now);
    scanf("%d",&l);
    memset(ans,'0',sizeof(ans));
    ans[0] = '1'; ans[104] = 0;
    ans2[0] = '1'; ans2[104] = 0;
    }

  • 1
    @ 2013-10-29 20:18:31

    虽然过了,但还是不理解,希望以后有能力了,再来重新刷吧.
    DXe-SYF

  • 1
    @ 2013-10-18 21:06:46

    测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 824 KiB, score = 10
    测试数据 #3: Accepted, time = 62 ms, mem = 828 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 824 KiB, score = 10
    测试数据 #5: Accepted, time = 62 ms, mem = 828 KiB, score = 10
    测试数据 #6: Accepted, time = 62 ms, mem = 824 KiB, score = 10
    测试数据 #7: Accepted, time = 62 ms, mem = 828 KiB, score = 10
    测试数据 #8: Accepted, time = 78 ms, mem = 828 KiB, score = 10
    测试数据 #9: Accepted, time = 78 ms, mem = 824 KiB, score = 10
    Accepted, time = 434 ms, mem = 828 KiB, score = 100

    3小时...连普及组的题都做得这么艰辛的我真是蒟蒻..

  • 1
    @ 2013-10-07 01:23:47

    测试数据 #0: Accepted, time = 15 ms, mem = 736 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 736 KiB, score = 10
    测试数据 #3: Accepted, time = 31 ms, mem = 732 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 736 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 732 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 732 KiB, score = 10
    测试数据 #7: Accepted, time = 46 ms, mem = 736 KiB, score = 10
    测试数据 #8: Accepted, time = 62 ms, mem = 736 KiB, score = 10
    测试数据 #9: Accepted, time = 62 ms, mem = 736 KiB, score = 10

  • 1
    @ 2013-04-08 11:41:26

    #include<iostream>
    #include<string>
    #include<string.h>
    #include<cstdlib>
    using namespace std;
    string s;
    int k;
    int a[101],b[101],w[101]={0};
    int gw[10]={1,1,4,4,2,1,1,4,4,2};
    int cheng[101]={0},bei[101]={0};
    void init()
    {
    int i;
    cin>>s>>k;
    w[0]=gw[s[s.length()-1]-'0'];
    for(i=0;i<s.length();i++)
    a[s.length()-i-1]=s[i]-'0';
    }
    void multi(int a[],int b[])
    {
    int i,j;
    int c[101];
    memset(c,0,sizeof(c));
    for(i=0;i<100;i++)
    for(j=0;j<100;j++)
    if(i+j<100)
    {
    c[i+j]+=a[i]*b[j];
    c[i+j+1]+=c[i+j]/10;
    c[i+j]=c[i+j]%10;
    }
    for(i=0;i<100;i++)
    {
    c[i+1]+=c[i]/10;
    c[i]=c[i]%10;
    }
    memcpy(b,c,sizeof(c));
    }
    int bj(int a[],int b[],int n)
    {
    int i;
    for(i=0;i<=n;i++)
    if(a[i]!=b[i])
    return 0;
    return 1;
    }

    void solve()
    {
    int i,j;
    int temp[101]={0};
    bei[0]=1;
    for(i=0;i<w[0];i++)
    {
    multi(a,bei);
    }
    for(i=1;i<k;i++)
    {
    memcpy(cheng,a,sizeof(a));
    memset(temp,0,sizeof(temp));
    temp[0]=1;
    for(j=1;j<=10;j++)
    {
    multi(bei,cheng);
    multi(bei,temp);
    if(bj(cheng,a,i)==1)
    {
    w[i]=j;
    memcpy(bei,temp,sizeof(temp));
    break;
    }
    }
    if(w[i]==0)
    {
    cout<<-1<<endl;
    exit(0);
    }

    }

    }
    void dmulti(int a[],int b)
    {
    int i;
    int c[101];
    memset(c,0,sizeof(c));
    for(i=0;i<100;i++)
    {
    c[i]+=a[i]*b;
    c[i+1]+=c[i]/10;
    c[i]=c[i]%10;
    }
    memcpy(a,c,sizeof(c));
    }
    void print()
    {
    int i,j;
    int ans[101]={0};
    ans[0]=1;
    for(i=0;i<k;i++)
    dmulti(ans,w[i]);
    i=100;
    while((ans[i]==0)&&(i>0))i--;
    for(j=i;j>=0;j--)cout<<ans[j];
    }
    int main()
    {
    init();
    solve();
    print();
    return 0;
    }

  • 1
    @ 2009-10-05 12:15:44

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    。。。C++的指针太脑残了。。。Answer的位数问题找了半天才找到。。交了我10次。。

  • 1
    @ 2009-10-01 00:19:58

    编译通过...

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

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

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

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

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

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

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

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

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

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

    没有任何优化...

    没想到普及组还有这么难的题目...

    做了我半年......

    • @ 2018-08-19 08:03:24

      那么久

  • 1
    @ 2009-09-28 11:41:01

    MD,本说随便找一道题来强J,结果反被强J!

    耻辱啊....

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 1
    @ 2009-09-21 01:09:00

    按位数逐渐递增的试探

    如果前i位的循环长度是k

    那么前i+1位的循环长度必为k的倍数,假设这个倍数为p

    用数论知识可以证明,如果p大于10那么,一定无解.

    只要用高精度乘法模拟,

    欧拉函数,快速幂什么的都可以不用

    要注意,高精要写两个,

    一个是试探循环长度的高精,只要乘k位

    另一个是答案的高精度乘法,因为只要乘p,p小于10,

    所以第二个乘法是单精度的,位数显然都要算.

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    这个是Vijos Sunny

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    这个是Vivid Puppy

    速度差这么多..

  • 0
    @ 2020-02-09 10:51:20

    #include<cstdio>
    #include<cstring>
    char c[109];int k,l,u;
    struct big{int a[109];}d,p,q,r,s,t;
    big mul(big x,big y){big z=d;int i,j;for(i=1;i<=k;++i){
    for(j=k-i+1;j;--j){z.a[i+j-1]+=x.a[i]*y.a[j];}
    }for(i=1;i<k;++i)z.a[i+1]+=z.a[i]/10,z.a[i]%=10;
    z.a[k]%=10;return z;}
    int main(){
    int i,j;scanf("%s%d",c,&k),l=strlen(c);
    for(i=(l<k?l:k);i;--i)p.a[i]=c[l-i]-48;r=p,t.a[l=1]=1;
    for(i=1;i<=k;++i){if(mul(p,r).a[i]==p.a[i])continue;u=1,s=r;
    do{r=mul(s,r),++u;if(u>10){puts("-1");
    return 0;}}while(mul(p,r).a[i]!=p.a[i]);for(j=1;j<=l;++j)t.a[j]*=u;
    for(j=1;j<l;++j)t.a[j+1]+=t.a[j]/10,t.a[j]%=10;if(t.a[l]>=10)t.a[l+1]+=t.a[l]/10,t.a[l++]%=10;
    }for(i=l;i;--i)printf("%d",t.a[i]);}

  • 0
    @ 2018-11-27 08:28:59

    卢本伟牛逼

  • 0
    @ 2018-10-13 10:44:39

    一道非常恶心的题目
    高精题

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int note[202],b[202],pd[202],ans[1001],q[202];
    int k,w,len;
    char s[202];
    inline int read()
    {
        int res=0,f=1,ch;
        while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-') f=-1;}
        while(ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar();
        return res*f;
    }
    inline void write(int x){   if(x==0){putchar(48);return;}   int len=0,dg[20];   while(x>0){dg[++len]=x%10;x/=10;}   for(int i=len;i>=1;i--)putchar(dg[i]+48);}
    inline void work()
    {
        memset(q,0,sizeof(q));
        for(register int i=1; i<=k; i++)
            for(register int j=1; j<=k; j++)
            {
                if(i+j-1<=k)
                    q[i+j-1]+=b[i]*pd[j];
                else
                    break;
            }
        for(register int i=1; i<=k; i++)
        {
            if(q[i]>=10)
            {
                q[i+1]+=q[i]/10;
                q[i]%=10;
                if(i+1>k)q[i+1]=0;
            }
        }
    }
    inline void di(int x)
    {
        for(register int i=1; i<=ans[0]; i++)
        {
            ans[i]=ans[i]*x;
        }
        for(register int i=1; i<=ans[0]; i++)
        {
            if(ans[i]>=10)
            {
                ans[i+1]+=ans[i]/10;
                ans[i]%=10;
                if(i+1>ans[0])
                    ans[0]++;
            }
        }
    }
    int main()
    {
        scanf("%s",s);k=read();
        w=1;
        len=strlen(s);
        for(register int i=1; i<=k; i++)
        {
            b[i]=note[i]=s[len-i]-'0';
        }
        ans[0]=ans[1]=1;
        while(w<=k)
        {
            memset(pd,0,sizeof(pd));
            pd[1]=1;
            work();
            swap(q,pd);
            int n=b[w];
            for(register int i=1; i<=11; i++)
            {
                work();
                if(q[w]==n)
                {
                    di(i);
                    swap(b,pd);
                    break;
                }
                swap(q,pd);
                if(i==11) {
                    printf("-1");
                    return 0;
                }
            }
            w++;
        }
        for(register int i=ans[0]; i>=1; i--)
            write(ans[i]);
        return 0;
    }
    

信息

ID
1032
难度
7
分类
高精度 点击显示
标签
递交数
4012
已通过
848
通过率
21%
被复制
22
上传者