我们考虑一下,在一个数组中找两个数,使得他们接在一起后是数x的倍数。
如何考虑呢?
如果暴力枚举一定会超时。
所以我们要考虑如何对每个数进行一次处理后就能很快的找到当前数的对应数能构成x的倍数。
这样,我们可以用同余定理得到:
( ( a * pow ( 10 , len ) ) % x + b % x ) % x
len表示b的位数长度。
从这个公式观察,我们想到可以使用离散来记录x内的余数的每个数中有多少个,然后我们还要分开数的长度来记录。
这样我们可以考虑用map来存储一个二维结构数据,形式为:
map[数的长度][数对x求余]
然后我门只需要遍历一次数组中的每个数a,然后再枚举一下未知数b的长度,可以快速统计a对应的数b。算法时间复杂度是O(n)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+5;
unordered_map<int,unordered_map<int,int>>mp;
//记录哈希过的数的个数:后面拼接的数的长度,取模11的余数
int sizes[N]; //记录当前第i个数的长度
void solve(){
int n;cin>>n;
vector<ll>arr(n+1);
for(int i = 1;i<=n;++i){
cin>>arr[i];
}
for(int i = 1;i<=n;++i){
ll x = arr[i];
int y = x%11;
string str = to_string(x);
int len = str.size();
mp[len][y]++; //记录对应的数的个数
sizes[i] = len; //存储当前第i个数的长度
}
ll res = 0;
for(int i = 1;i<=n;++i){
ll x = arr[i];
int xy = x%11; //考虑容斥原理,原本的数的取模,避免在计数时重复计算
for(int j = 1;j<=9;++j){ //枚举后面的数的长度
ll xx = x * pow(10LL,j);
int y = xx%11; //对前面的数xx取模
int d = (11 - y)%11; //加上后面对应的膜能能被11整取
if(j==sizes[i]&&d==xy)res += mp[j][d]-1; //如果本数x在对应统计数组中就减去自身
else res += mp[j][d];
}
}
cout<<res<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}