2016"百度之星" - 初赛（Astar Round2A）--HDU 5690 |数学转化+快速幂

Sample Input

1 3 5 2

1 3 5 1

3 5 99 69

Sample Output

Case #1:

Case #2:

Yes

Case #3:

Yes

Hint

对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。

解：

m个x组成的数可以表示为x*(1+10+10^²+...+10^^m-1)=x*(10^^m-1)/9;

即x*(10^^m-1)/9%k==c

x*(10^^m-1)%(9*k)==9*c?

那么我们就是要求x*(10^m-1)/9 MOD k是不是==c那么，这里有一个分母我们怎么处理呢，肯定有人在想求逆元呀，但是 GCD(9,k)不一定等于1呀，所以求逆元的方法不能用了，那么怎么办呢，我们可以同时扩大9倍也就是求的 x * (10^m-1)MOD 9k 是不是等于 9 * c，剩下的就是
快速幂了。

#include "cstdio"

#define LL long long

LL quick_mod(LL a,LL b,LL mod)

{

    LL ans=;

    while(b>)

    {

        if(b&){

            ans=ans*a%mod;

        }

        a=a*a%mod;

        b>>=;

    }

    return ans;

}

int main()

{

    LL T,x,m,k,c;

    scanf("%lld",&T);

    int con=;

    while(T--)

    {

        scanf("%lld%lld%lld%lld",&x,&m,&k,&c);

        printf("Case #%d:\n",con++);

        LL mod=*k;

        LL ans=quick_mod(,m,mod)*x%mod-x;

        if(ans==*c)

            printf("Yes\n");

        else

            printf("No\n");

    }

    return ;

}

巴特西

2016"百度之星" - 初赛（Astar Round2A）--HDU 5690 |数学转化+快速幂

最新文章

热门文章