前言
t
a
g
:
tag :
tag: 数学
传送门 :
题意 :
寻找满足
a
i
a
j
a_ia_j
aiaj能被
k
k
k整除的数对数量
思路 :
我们可得公式 :
( a i ∗ T + a j ) % k = 0 (a_i*T + a_j)\%k=0 (ai∗T+aj)%k=0
a
[
i
]
∗
T
%
k
=
x
1
a[i]*T\%k =x_1
a[i]∗T%k=x1
a
[
j
]
%
k
=
x
2
a[j]\%k =x_2
a[j]%k=x2
x
1
+
x
2
=
k
x_1+x_2=k
x1+x2=k
形如 x 1 + x 2 = k x_1+x_2 =k x1+x2=k我们都可以用 m a p map map解决
不过这次带有一个 T T T
我们可以枚举 a i a_i ai当作尾数,因此我们需要预处理 a i a_i ai的位数
因为 a i < = 1 0 9 a_in>>k; Fup(i,1,n){ cin>>a[i]; ll temp = a[i]; if(temp == 0) cnt[i] = 1; else{ while(temp){ ++cnt[i]; temp/=10; } } mp[cnt[i]][a[i]%k]++; } Fup(i,1,n){ ll x = a[i]; Fup(j,1,10){ x = x*10%k; if(mp[j].find((k-x)%k)!= mp[j].end()){ ans += mp[j][(k-x)%k]; if(cnt[i] == j && a[i]%k == (k-x)%k) --ans; } } } cout
