10.10 T1

温栀槿 · 2018-10-10 20:00:37 · 个人记录

给你一个数x，有一个长度为n的数，每一位都是x，求它对p的余数

Solution：

我们考虑当p为质数时，答案为

( qpow(10,n)-1) / 9 )*x%p;

处理9关于p的逆元即可

但如果p不是质数呢？

我们考虑

（A/B）% P =(A%(P*B)) / B

证明如下：

设(A/B)%P=R

==>> A/B=P*K+R

A=PBK+R*B

A % PB=RB

(A%(P*B)) / B= R =(A/B)%P

所以把p*9，最后答案/9即可

#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll q,x,n,p;

ll qpow(ll a,ll b){
    ll ans=1,x=a;
    while(b){
        if(b&1) ans*=x;
        ans%=p;
        x=x*x;
        x%=p;
        b>>=1;
    }
    return ans;
}

ll paow(ll a,ll b){
    ll ans=1,x=a;
    while(b){
        if(b&1) ans*=x;
        x=x*x;
        b>>=1;
    }
    return ans;
}

int main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%lld",&q);
    while(q--){
        scanf("%lld%lld%lld",&x,&n,&p);
//      if(__gcd(9ll,p)==1){
//      ll ans=(paow(10,n)-1)/9*x%p;
//      printf("%lld\n",ans);
//      continue;
//      }
        p=p*9;
        ll ans=((qpow(10,n)-1)%p+p)%p*x%p;
//      ll inv=qpow(9,p-2);
        ans=ans/9;
        printf("%lld\n",ans);
    }
}