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
