题解 P1965 【转圈游戏】

ミク · 2018-07-21 20:41:02 · 题解

看到题解都在说快速幂，有点懵圈，实际上这道题是可以不用快速幂的，看起来不用快速幂的话就必须暴力乘10并取模共1e9次，想这样：

#include<cstdio>
using namespace std;
int n,m,k,x;
int a[1000005];
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&x);
    int i;a[0]=x;
    for(i=1;;i++) {
        x+=m;
        if(x>=n) x-=n;
        a[i]=x;
        if(x==a[0]) break;
    }
    int q=1;
    for(int j=1;j<=k;j++) q=q*10%i;
    printf("%d",a[q]);
    return 0;
}

然而这样的话复杂度是O（n+k），肯定会TLE的。但是注意到n的范围是1e6，也就是说不需要每次乘十取模，乘上1e10也是不会爆long long的。也就是说我们把时间优化到了原来的十分之一。

AC代码：

#include<cstdio>
using namespace std;
int n,m,k,x;
int a[1000005];
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&x);
    long long i;a[0]=x;
    for(i=1;;i++) {
        x+=m;
        if(x>=n) x-=n;
        a[i]=x;
        if(x==a[0]) break;
    }
    int l=k/10,r=k%10;
    int q=1;
    for(int j=1;j<=l;++j) q=q*10000000000%i;
    for(int j=1;j<=r;++j) q=q*10%i;
    printf("%d",a[q]);
    return 0;
}