acwing2068. 整数拼接

题目

题解

求(a[j]*10^{k[i]+a[i])%k=0的个数，即求a[j]*10}k[i]%k=-a[i]%k

#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N],s[11][N];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        LL t=a[i]%k;
        for(int j=0;j<11;j++){
            s[j][t]++;
            t=t*10%k;
        }
    }
    LL ans=0;
    for(int i=0;i<n;i++){
        LL t=a[i]%k;
        int len=to_string(a[i]).size();
        ans+=s[len][(k-t)%k];
        LL r=t;
        while(len--)r=r*10%k;
        if(r==(k-t)%k)ans--;
    }
    cout<<ans<<endl;
    return 0;
    
}