考察:枚举 + hash
思路:
暴力是直接枚举a[i]与a[j],需要优化省去一重循环.我们枚举的a[i],a[j]检查是否为k倍数时,需要让a[j]*10t + a[i](t位为a[i]的位数,注意这里用字符串转换反而不如直接求位数方便).一重循环枚举a[i]时,t已知,a[i]已知,剩下的是快速找符合条件的a[j].这里可以想到同余,即a[i]%k+a[j]*10t%k == 0.前者已知,我们可以考虑预处理后者.可以用二维数组存储每一个t,a数组%k的余数.时间复杂度为10*N.
注意:a[i]与a[j]*10t的余数相同时,需要将ans-1
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int N = 100010,M = 11; 8 int a[N],h[M][N]; 9 LL ans; 10 int main() 11 { 12 int n,k; 13 scanf("%d%d",&n,&k); 14 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 15 for(int i=1;i<=n;i++) 16 { 17 int c = 1; LL t = 10; 18 while(c<11) 19 { 20 h[c][a[i]*t%k]++; 21 c++; 22 t=10*t%k; 23 } 24 } 25 for(int i=1;i<=n;i++) 26 { 27 int s = a[i],t = a[i]%k,cnt = 0; 28 while(s) s/=10,cnt++; 29 ans+=h[cnt][(k-a[i]%k)%k]; 30 if(h[cnt][(k-a[i]%k)%k]&&t==(k-a[i]%k)%k) ans--; 31 } 32 printf("%lld\n",ans); 33 return 0; 34 }