题解：AT_abc433_d [ABC433D] 183183

思路

将函数转化为

f(A_i,A_j)\bmod M=(A_i\times 10^{d}+A_j) \bmod M=0

其中

d=\lfloor\log_{10}A_j\rfloor +1

。

暴力枚举

i,j

会超时。

进一步转化

(A_i\times 10^{d}\bmod M+A_j\bmod M) \bmod M=0

。

令

r_1=A_i\times 10^{d}\bmod M,r_2=A_j\bmod M

。

考虑

A_j

确定时，

r_2

确定进一步可以算出

r_1

。则若能统计

A_i\times 10^{d}\bmod M

余数为

r_2

的个数，累加给答案即可。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<pair<int, int>, int> mp;
ll n, m, ans, base[15], a[200005], l[200005];
int cal(int n) {
	int len = 0;
	do {
		len++;
		n /= 10;
	} while (n);
	return len;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	base[0] = 1;
	for (int i = 1; i <= 10; i++) base[i] = base[i - 1] * 10;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		l[i] = cal(a[i]);
		for (int d = 1; d <= 10; d++) {
			int r = a[i] % m  * base[d] % m;
			mp[make_pair(d, r)]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		int r = (m - a[i] % m) % m;
		ans += mp[make_pair(l[i], r)];
	}
	cout << ans;
	return 0;
}

题解：AT_abc433_d [ABC433D] 183183

文章操作

思路

代码

相关推荐

评论

题解：AT_abc433_d [ABC433D] 183183