[Acwing] 第 67 场周赛

前言

t a g : tag : tag: 数学 传送门 :

题意 : 寻找满足 a i a j a_ia_j ai​aj​能被 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