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

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

2024-11-17 15:51:02   203人阅读

 

 

技术分享

Sample Input
3
1 3 5 2
1 3 5 1
3 5 99 69
 
Sample Output
Case #1:
No
Case #2:
Yes
Case #3:
Yes
Hint
对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。
 
解：
m个x组成的数可以表示为x*(1+10+10^2+...+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=1;
    while(b>0)
    {
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    LL T,x,m,k,c;
    scanf("%lld",&T);
    int con=1;
    while(T--)
    {
        scanf("%lld%lld%lld%lld",&x,&m,&k,&c);
        printf("Case #%d:\n",con++);
        LL mod=9*k;
        LL ans=quick_mod(10,m,mod)*x%mod-x;
        if(ans==9*c)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

 

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


联系
我们