题解 P1965 【转圈游戏】

LGG_ · 2019-08-05 17:03:36 · 题解

这是一道提高组的省选题； 刚看的时候觉得简单（貌似每道题都是）

先看一种暴力的小解法（30分）

int n,m,k,x,y,c;
int a[1000000];
int main()
{
    cin>>n>>m>>k>>x;
    for(int i=0;i<pow(10,k);i++)
    {
        x+=m;
        if(x>=n)x-=n;//多了的减去    
    }
    cout<<x;
}

甚至可以优化一下

long tr(long long x)//pow（10，5）=9999我也很绝望
{
    int u=10;       //还不知道为什麽9999；。。
    for(int i=1;i<x;i++)
    {
        u*=10;
    }
    return u;
}
int main()
{
    cin>>n>>m>>k>>x;
    mm=tr(k);
    c=mm/n;
    ans=mm-n*c;
    if(k==0||ans==0){
        cout<<x;
        return 0;
    }
    for(int i=0;i<ans;i++)
    {
        x+=m;
        if(x>=n)x-=n;   
    }
    cout<<x;
}

然而只是TLE变成了WA

正当我绝望的时候突然发现是不是10的k次方的的问题之后

。。。。。。。。

快速幂一个好东西

int tr(int a,int b)
{
    int re=1,t=a;
    while(b)
    {
        if(b&1)re=re*t;//b初以2等于1的话就不执行
        t=t*t;
        b>>=1;
    }
    return re;
}

+大佬公式

这不就好了吗

#include<iostream>
using namespace std;
int n,m,k,x,y,c;
int tr(int a,int b)
{
    int re=1,t=a;
    while(b)
    {
        if(b&1)re=re*t%n;
        t=t*t%n;
        b>>=1;
    }
    return re;
}
int main()
{
    cin>>n>>m>>k>>x;
    cout<<(x%n+m%n*tr(10,k)%n)%n;
    return 0;
}

做完了其实感觉挺简单。。（看破不说破）