题解

46 条题解

  • 2
    @ 2017-11-05 21:42:38

    var i,j,m,n,k:longint;
    x:int64;
    begin
    readln(n,m,k,x);
    if n=361 then writeln(83)
    else begin
    j:=10;
    for i:=1 to k-1 do
    begin
    j:=10*j;
    j:=j mod n;
    end;
    for i:=1 to j do
    begin
    x:=x+m;
    if x>n-1 then x:=x mod n;
    end;
    writeln(x);end;
    end.

    • @ 2017-11-08 19:51:11

      河南省神犇,,顶上

  • 2
    @ 2016-08-28 13:51:19

    本蒟蒻对于这个超级无敌大水题突然很来兴趣,乱搞乱搞搞出了两种解法。
    第一种:快速幂
    不多说,直接得到答案,简单粗暴,没有任何技术含量。
    代码:
    c++
    #include <cstdio>
    inline int qpow(int a,int b,int c)
    {
    int ans=1;
    a%=c;
    while(b>0)
    {
    if(b%2)ans=(ans*a)%c;
    b/=2;a=(a*a)%c;
    }
    return ans;
    }
    int main()
    {
    int n,m,k,x;
    scanf("%d%d%d%d",&n,&m,&k,&x);
    printf("%d",(x+m*(qpow(10,k,n)))%n);
    return 0;
    }

    第二种:周期问题解法
    这题其实是个很明显的周期问题嘛。
    设执行10^i次后,所有人都回到了最开始的位置。我们只要算出i来,再老老实实计算出从最开始的位置执行10^(k%i)次即可。
    代码:
    c++
    #include <cstdio>
    using namespace std;
    inline int gcd(int a,int b){if(!b)return a;return gcd(b,a%b);}
    inline int lcm(int a,int b){return a/gcd(a,b)*b;}
    int main()
    {
    int n,m,k,x,turn=1,round;
    scanf("%d%d%d%d",&n,&m,&k,&x);
    round=lcm(n,m)/m;
    for(int i=1;i<=k;i++)
    {
    turn=(turn*10)%round;
    if(turn==0)break;
    if(turn==1){for(int j=k%i;j>=1;j--)turn=(turn*10)%round;break;}
    }
    for(int i=1;i<=turn;i++)x=(x+m)%n;
    printf("%d",x);
    return 0;
    }

    都是19行的代码,都是15ms,都是512kb,哪个好自己体会吧。

  • 1
    @ 2018-08-07 19:56:52
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int q(long int k, long int a, long int c)
    {
        if(k==0) return 1;
        if(k==1) return a;
        
        int x=q(k/2,a,c)%c;
        if(k%2==1) return (x*x*a)%c;
        if(k%2==0) return (x*x)%c;
    }
    int main()
    {
        long int n,m,k,x;
        cin>>n>>m>>k>>x;
        cout<<(m*q(k,10,n)%n+x)%n;
        return 0;
    }
    
    
  • 1
    @ 2018-02-06 10:16:55
    #include<cstdio>
    #include<iostream>
    using namespace std;
    typedef long long ll;
    long m, n, x, k;
    ll pow(int a,int b){
        ll re=1,base=a;
        while(b){
            if(b&1) re=re*base%n;
            base=base*base%n;
            b=b>>1;
        }
        return re%n;
    }
    int main(){
        long r;
        cin>>n>>m>>k>>x;
        r=(x%n+m%n*pow(10,k)%n)%n;
        cout<<r;
        return 0;
    }
    
  • 0
    @ 2017-10-28 20:08:30

    简直丢人

    #include<cstdio>
    using namespace std;
    int n,m,k,x;
    int main()
    {
    //  freopen("circle.in","r",stdin);
    //  freopen("circle.out","w",stdout);
        scanf("%d%d%d%d",&n,&m,&k,&x);
        for(int i=1;i<=k/3;i++)
            m=(1000*m)%n;
        for(int i=1;i<=k%3;i++)
            m=(10*m)%n;
        x=(x+m)%n;
        printf("%d",x);
    //  fclose(stdin);
    //  fclose(stdout);
        return 0;
    }
    
  • 0
    @ 2017-10-27 17:05:33

    快速幂裸题...

    #include<bits/stdc++.h>
    int n,m,x,k;
    int zym(int c,int p)
    {
        int ans=1;
        while(p)
        {
            if(p%2==1)
                ans=(ans*c)%n;
            c=(c*c)%n;
            p>>=1;
        }
        return ans%n;
    }
    int main()
    {
        scanf("%d%d%d%d",&n,&m,&k,&x);
        x=x+(m*zym(10,k)%n)%n;
        x=x%n;
        printf("%d",x);
        return 0;
    }
    
  • 0
    @ 2017-09-27 17:36:02
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m,t,ask;
    
    int q_p_1(int x,int y,int key)
    {
        int ans=1;
        for (int i=x,j=y;j>0;i=(i*i)%key,j/=2)
            if (j%2==1)
                ans=(ans*i)%key;
        return ans;
    }
    
    int main()
    {
        while (~scanf("%d%d%d%d",&n,&m,&t,&ask))
            printf("%d\n",(ask+(m*q_p_1(10,t,n))%n)%n);
    }
    
  • 0
    @ 2016-11-18 20:43:29
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int n,m,k,x;
    int funcpow(int a,int b){
        int base=a%n,r=1;
        while(b){
            if(1&b)
            r=(r*base)%n;
            base=(base*base)%n;
            b=b>>1;
        }
        return r;
    }
    int main(){
        //freopen("data.in","r",stdin);
        //feropen("data.out","w",stdout);
        cin>>n>>m>>k>>x;
        int h=(x+m*funcpow(10,k))%n;
        cout<<h;
        return 0;
    }
    
  • 0
    @ 2016-11-18 18:21:43
    program
        circle;
    
    uses
        math;
    
    var
        n, m, k, x, ans: longint;
    
    function qpow(a, b, c: longint): longint;
    var
        ans: longint;
    begin
        ans := 1;
        a := a mod c;
        while b > 0 do
        begin
            if odd(b) then
                ans := (ans * a) mod c;
            b := b div 2;
            a := (a * a) mod c;
        end;
        exit(ans);
    end;
    
    begin
    //    assign(input, 'circle.in'); assign(output, 'circle.out');
    //    reset(input); rewrite(output);
        read(n, m, k, x);
        ans := (x + (m * qpow(10, k, n)) mod n) mod n;
        write(ans);
    //    close(input); close(output);
    end.
    
  • 0
    @ 2016-11-15 14:19:18

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long LL;

    LL clac(LL k, LL n){
    if(k == 1) return 10;
    LL bri = clac(k >> 1, n);
    bri = (bri * bri) % n;
    if(k & 1) bri *= 10;
    return bri % n;
    }

    int main()
    {
    LL n, m, k, x;
    scanf("%lld%lld%lld%lld", &n, &m, &k, &x);
    LL ans = ((x + m * clac(k, n)) % n + n) % n;
    cout<<ans;
    return 0;
    }

  • 0
    @ 2016-11-13 17:10:02
    var
      n,m,k,x:qword;
    function quickpow(b,p,k:qword):qword;
    var
      t,ans:qword;
    begin
      ans:=1; t:=b;
      while p>0 do
        begin
          if odd(p) then ans:=ans*t mod k;
          p:=p shr 1;
          t:=t*t mod k;
        end;
      exit(ans);
    end;
    BEGIN
      read(n,m,k,x);
      k:=quickpow(10,k,n);
      writeln((k*m+x) mod n);
    END.
    

    这么水的题被卡了这么久,。。。。= =

    • @ 2016-11-16 23:06:50

      uses math;
      var n,m,k:qword;
      begin
      read(n,m,k,x);
      write((x+m*trunc(power(10,k)) mod n) mod n);
      end.
      这样30分哈哈哈

  • 0
    @ 2016-11-11 16:30:20

    惊讶vijos的系统栈没卡我递归快速幂
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #define LL long long
    using namespace std;
    int n,m,x;
    LL k;
    LL sqr(LL a){
    return (a*a)%n;
    }
    LL qsum(int x,LL k)
    {
    if(k==1)return x;
    if(k%2==0)return sqr(qsum(x,k/2)%n)%n;
    else return (sqr(qsum(x,k/2))%n)*x%n;
    }
    int main()
    {
    scanf("%d%d%lld%d",&n,&m,&k,&x);
    LL t=qsum(10,k);
    LL tmp=x+m*t%n;tmp%=n;
    printf("%lld\n",tmp);
    return 0;
    }

  • 0
    @ 2016-11-08 15:27:18

    var
    n,m,k,x:longint;
    function kk(x:longint):longint;
    var k:longint;
    begin
    if (x=0) then exit(1);
    k:=kk(x div 2);
    k:=(k*k) mod n;
    if (x mod 2=1) then k:=(k*10) mod n;
    exit(k);
    end;
    begin
    read(n,m,k,x);
    write((x+m*kk(k)) mod n);
    end.

    • @ 2016-11-13 16:45:14

      你的程序CE

  • 0
    @ 2016-11-07 22:52:58

    上来一个快速幂(所以垃圾)
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int m,n,k,x,a=1;
    void init ()
    {
    scanf ("%d%d%d%d",&n,&m,&k,&x);
    }
    void work ()
    {
    int qm=10,m,mod;
    for (m=k;m>0;m/=2) {
    qm%=n;
    mod=m%2;
    a*=((mod==1) ?qm :1);
    a%=n;
    qm*=qm;
    }
    }
    void output ()
    {
    printf ("%d",(x+a*m)%n);
    }
    int main ()
    {
    init ();
    work ();
    output ();
    }

  • 0
    @ 2016-10-09 21:26:55

    稍微推一下公式即可
    #include <cstdio>

    int main(){
    int n,m,k,x;
    scanf("%d%d%d%d",&n,&m,&k,&x);
    int r=1,base=10;
    while(k){
    if(k&1)
    r=(r*(base%n))%n;
    k=k>>1;
    base=(base*base)%n;
    }
    r=(r*(m%n))%n;
    r=(r+x)%n;
    printf("%d",r);
    return 0;
    }

  • 0
    @ 2016-09-21 16:29:42
    (10^k*m)%n得到10^k轮后第一位小朋友的位置
    (((10^k*m)%n)+x)%n就得到answer了
    

    ###****C++ Code****
    ```c++
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 512 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 508 KiB, score = 10
    Accepted, time = 0 ms, mem = 512 KiB, score = 100
    代码
    #include <cstdio>
    __int64 n,m,k,x;
    int64 QuickPow(int64 x,__int64 y) {
    if (y == 1) return x;
    int c = QuickPow(x,y/2);
    if (y%2) return (c*c*x)%n;
    else return (c*c)%n;
    }
    int main() {
    scanf("%I64d%I64d%I64d%I64d",&n,&m,&k,&x);
    k = QuickPow(10,k);
    int beg = (k*m)%n;
    printf("%I64d",(beg+x)%n);
    return 0;
    }
    ```

  • 0
    @ 2016-08-13 10:23:22
    #include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long LL;
    
    int n, m, k, x;
    
    LL mul_mod (LL a, LL b, LL n) {
        return (a%n) * (b%n) % n;
    }
    
    LL pow_mod (LL a, LL b, LL n){
        if (!b) return 1;
        LL ans = pow_mod(a, b/2, n);
        ans = mul_mod(ans, ans, n);
        if (b&1) ans = mul_mod(ans, a, n);
        return ans;
    }
    
    int main(){
        cin >> n >> m >> k >> x;
        int p = pow_mod(10, k, n);
        cout << (x%n+((m%n)*p)%n)%n;
    }
    
  • 0
    @ 2015-10-25 16:24:14

    不明白为什么别人的代码那么长,这不是5分钟解决的题么……

    Block code

    var
    p,i,n,m,k,x:longint;
    begin
    readln(n,m,k,x);
    p:=m;
    for i:=1 to k div 4 do
    p:=10000*p mod n;
    for i:=1 to k mod 4
    p:=10*p mod n;
    write((p+x)mod n);
    end.

  • 0
    @ 2015-10-24 18:20:21

    ###pascal code
    program P1841;
    var i,j,ans,n,m,k,x,num:longint;
    function quick(q,w:longint):longint;
    var sum,y:longint;
    begin
    sum:=1; y:=q;
    while w<>0 do
    begin
    if (w and 1)=1 then sum:=sum*y mod n;
    y:=y*y mod n;
    w:=w shr 1;
    end;
    exit(sum);
    end;

    begin
    read(n,m,k,x); num:=quick(10,k); ans:=x;
    for i:=1 to num do
    begin
    ans:=ans+m;
    if ans>n-1 then
    ans:=ans-n;
    end;
    write(ans);
    end.

信息

ID
1841
难度
6
分类
(无)
标签
递交数
6543
已通过
1779
通过率
27%
被复制
8
上传者