用map是卡着过去的。。题解用vector+离散化后常数小了十倍。。
总之就是把所有模数给保存下来然后离散化,再去匹配一下即可,最后有个细节
自己的
#include<bits/stdc++.h> using namespace std; #define ll int #define maxn 200005 ll n,k,a[maxn]; map<ll,ll>mp[11]; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); ll tmp=a[i],len=0; while(tmp)len++,tmp/=10; mp[len][a[i]%k]++; } ll ans=0; for(int i=1;i<=n;i++){ ll tmp=a[i],tmp2=a[i],len=0; while(tmp2)len++,tmp2/=10; for(int j=1;j<=10;j++){ tmp=tmp*10%k; ans+=mp[j][(k-tmp)%k]; if(j==len && a[i]%k==(k-tmp)%k)ans--; } } cout<<ans<<endl; }
题解的
#include <bits/stdc++.h> #define forn(i, n) for (int i = 0; i < int(n); i++) typedef long long li; using namespace std; const int N = 200 * 1000 + 13; const int LOGN = 11; int n, k; int a[N]; int len[N]; vector<int> rems[LOGN]; int pw[LOGN]; int main() { scanf("%d%d", &n, &k); forn(i, n) scanf("%d", &a[i]); pw[0] = 1; forn(i, LOGN - 1) pw[i + 1] = pw[i] * 10 % k; forn(i, n){ int x = a[i]; while (x > 0){ ++len[i]; x /= 10; } rems[len[i]].push_back(a[i] % k); } forn(i, LOGN) sort(rems[i].begin(), rems[i].end()); li ans = 0; forn(i, n){ for (int j = 1; j < LOGN; ++j){ int rem = (a[i] * li(pw[j])) % k; int xrem = (k - rem) % k; auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem); auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem); ans += (r - l); if (len[i] == j && (rem + a[i] % k) % k == 0) --ans; } } printf("%lld\n", ans); return 0; }