题解 | #小莫的字符#

c题解，思路看代码处

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>


using namespace std;
int const mod=1e9+7;    //1e9+7
int const N=1e5+7;
int const INF=0x3f3f3f3f;

typedef long long LL;
typedef pair<int,int>PII;

#define x first
#define y second
#define ls u<<1
#define rs u<<1|1

int T;
int n,m;
int a[N];

void init(){
    
}

//返回余数
LL divider(vector<int> &A,LL b){
    vector<int>res;
    
    LL t=0;
    for(int i=0;i<n;i++){
        t=t*10+A[i];
        res.push_back(t/b);
        t%=b;
    }
    
    return t;   
    
}

/*
思路：
设x=(a0+a1*k+a2*k^2+a3*k^3...)
1.t=x(mod k)  t=x%k  模k后 得t=a0(模k的余数)
2.(1+x-t)=1+a1*k+a2*k^2+a3*k^3.. 模k^2后 1+a1*k
3.(1+a1*k)^x 二项是展开模k^2后 (1+x*a1*k)%(k^2)
4.对x%(k^2)：x%k^2=a0+a1*k,即a1=(x%k^2-a0)/k  
5将数据代入此式即为答案(1+x*a1*k)%(k^2)
*/

void solve()
{
    string s;   cin>>s; 
    n=s.size();
    int k;  cin>>k;
    vector<int>A;
    for(int i=0;i<n;i++)    A.push_back(s[i]-'0');
    
    LL K=1LL*k*k;
    LL t=divider(A,k); //模k的余数
    LL r1=divider(A,K);   //模k^2的余数
    
    LL a1=(r1-t)/k;
    cout<<(1+t*a1%K*k)%K;
} 

int main()
{
    T=1;
    //scanf("%d",&T);
    
    init();
    
    while(T--){
        solve();
    }
	
	return 0;
}