---
title: Codeforce 1029 D. Concatenated Multiples 解析(思維)
description: "Codeforce 1029 D. Concatenated Multiples 解析(思維)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1029 D. Concatenated Multiples 解析(思維)">
<!-- toc -->

# Codeforce 1029 D. Concatenated Multiples 解析(思維)
今天我們來看看CF1029D
[題目連結](https://codeforces.com/problemset/problem/1029/D)

> **題目**
給你一個序列$a$和一個數字$k$，求有幾種indices pair可以讓兩個數字串接在一起之後可以被$k$整除。

### 前言
set,map這些東西的常數真的有夠高阿

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
$a_i$和$a_j$串接起來是$a_i\times 10^{digit(a_j)}+a_j$，我們固定一個$a_i$和$digit(???)$，要看看哪些$a_j$符合長度是$digit(???)$和串接起來可被整除。

實作細節:我們可以先把相同長度的$a_j$放到一個$vector$裡，並且接著$a_j\%=k$。
如此一來決定了$a_i\times 10^{digit(???)}\mod k$是多少以後，只需要找到在同樣長度的$a_j$中，哪些剛好$=(k-(a_i\times 10^{digit(???)}\mod k))\mod k$，而又因為我們已經把$a_j\%=k$過了，所以可以在$sort$過同樣長度的$a_j$後，直接$upperbound-lowerbound$找同樣值的元素有多少個。
還有，$digit(a_j)$的其中一種求法是$digit(a_j)=1+log10(a_j)$

其實我一開始是用$map$實作的，想法是固定$a_j$然後看看$map$裡又多少個$a_i\times 10^{digit(???)}$剛好可以符合要求，然後從前往後+從後往前各看一次。然而這題的$k\le1e9$，因此$map$非常可能需要$insert$非常多空白元素，造成TLE，其中一部分造成TLE的原因是因為$insert$時要$allocate$新記憶體位置，這樣造成非常大的常數。

### 程式碼(正常作法):

const int _n=2e5+10;
int t,n,k,a[_n],dig[_n],ten[11];
VI d2a[_n];
ll ans;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>k;rep(i,0,n)cin>>a[i];ten[0]=1;rep(i,1,11)ten[i]=1ll*ten[i-1]*10%k;
  rep(i,0,n)dig[i]=1+log10(a[i]),a[i]%=k,d2a[dig[i]].pb(a[i]);
  rep(i,1,11)sort(all(d2a[i]));
  rep(i,0,n)rep(j,1,11){
    t=k-1ll*a[i]*ten[j]%k;if(t==k)t=0;
    ans+=upper_bound(all(d2a[j]),t)-lower_bound(all(d2a[j]),t);
    if(dig[i]==j and a[i]==t)ans--;
  }cout<<ans<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/1029/submission/91926412)

### 程式碼(改成unordered_map以後1800ms的AC):

const int _n=2e5+10;
int t,n,k,a[_n];
ll ans;
ll ten[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000ll};
struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator() (const std::pair<T1, T2> &pair) const
	{
		return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	}
};
unordered_map<PII,int,pair_hash> mp;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>k;rep(i,0,n)cin>>a[i];
  rep(i,0,n){
    ans+=mp[{(k-a[i]%k)%k,1+log10(a[i])}];
    rep(j,1,11)mp[{(1ull*a[i]*ten[j])%(1ull*k),j}]++;
  }mp.clear();
  per(i,0,n){
    ans+=mp[{(k-a[i]%k)%k,1+log10(a[i])}];
    rep(j,1,11)mp[{(1ull*a[i]*ten[j])%(1ull*k),j}]++;
  }cout<<ans<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/1029/submission/91922533)