C++整數(shù)拼接技巧大揭秘
問題描述：
給定一個長度為n的數(shù)組,A1,A2,...,An你可以從中選出兩個數(shù)Ai和Aj(i≠j)，然后將Ai和Aj一前一后拼成一個新的整數(shù)。例如12和345可以拼成12345或34512。注意交換Ai和Aj的順序總是被視為兩種拼法，即便Ai=Aj。請你計算有多少種拼法，滿足拼出的整數(shù)就是k的倍數(shù)。
輸入格式：
第一行包含兩個整數(shù)n和k。
第二行包括n個整數(shù)A1,A2,...,An。
輸出格式：
一個整數(shù)，代表答案。
例如輸入：4 2
1 2 3 4
輸出：6
規(guī)定：
對于30%的評測用例，1≤n≤1000，1≤K≤20，1≤Ai≤10^4
對于所有評測用例:1≤n≤10^5，1≤K≤10^5，1≤Ai≤10^9
分析：
拼接兩個整數(shù)（如12和345），得到12×1000+345=12345或345*100+12=34512。因此可以得到一個數(shù)學(xué)等式：拼起來的值為Ai×10^len(Aj)+Aj。
固本題要求滿足以下等式的Ai和Aj組合：（Ai×10^len(Aj)+Aj）%K=0-->（（Ai×10^len(Aj)）%K+Aj%K）%K=0
該式中，將計算拆分成兩部分：Q=（Ai×10^len(Aj)）%K和P=Aj%K。
（Q+P）%K=0-->Q=（K-P）%K
Q：有兩個未知量Ai的值和Aj的長度。
P：有一個未知量Aj的值。
當(dāng)確定Aj時就可以確定P，通過P的值與K的值，就可以通過Q=（K-P）%K得到Q的值。
結(jié)論：當(dāng)確定Aj時，就可以確定Q和Aj的長度，此時只需要查看有多少個Ai可滿足即可。
C++程序：
#include<iostream>
#include<string>
using namespace std;
typedef long long LL;
const int N=100010;
int s[11][N];//表示某個數(shù)*10^i%k==j的數(shù)量
int n;//表示將要輸入的n個數(shù)
LL a[N];//存放n個數(shù)
int k;//表示k倍
LL res;//表示結(jié)果
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
LL t=a[i]%k;
for(int j=0;j<11;j++)
{
s[j][t]++;
t=t*10%k;
}
}
for(int i=0;i<n;i++)
{
LL t=a[i]%k;
int len=to_string(a[i]).size();
res+=s[len][(k-t)%k];
LL r=t;
while(len--)
{
r=r*10%k;
}
if(r==(k-t)%k)
{
res--;
}
}
cout<<res<<endl;
return 0;
}此題比較考腦子（較難），可以用偽C或自然語言舉幾個例子，方便弄懂！
到此這篇關(guān)于C++整數(shù)拼接技巧大揭秘的文章就介紹到這了,更多相關(guān)C++ 整數(shù)拼接內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(76.最小窗口子串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(76.最小窗口子串),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
你以為將new替換為make_shared就萬事大吉嗎,真相是智能指針的陷阱比手動管理更隱蔽更危險,本文將深入剖析循環(huán)引用,性能陷阱和線程安全,希望對大家有所幫助2025-12-12
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡單貪吃蛇游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
這篇文章主要介紹了C語言中回調(diào)函數(shù)的使用詳情,閱讀下文我們將學(xué)習(xí)到架構(gòu)的核心理念和需、回調(diào)函數(shù)的作用、回調(diào)函數(shù)的程序編寫等內(nèi)容，需要的小伙伴可以參考一下2022-03-03
這篇文章主要介紹了C++設(shè)計模式之建造者模式,一個復(fù)雜對象是由多個部件組成的,建造者模式是把復(fù)雜對象的創(chuàng)建和部件的創(chuàng)建分別開來,分別用Builder類和Director類來表示,需要的朋友可以參考下2014-09-09
ProtoBuf全稱：protocol buffers,直譯過來是：“協(xié)議緩沖區(qū)”,是一種與語言無關(guān)、與平臺無關(guān)的可擴(kuò)展機(jī)制,用于序列化結(jié)構(gòu)化數(shù)據(jù),這篇文章主要介紹了C/C++ProtoBuf使用,需要的朋友可以參考下2024-01-01
C語言實(shí)現(xiàn)ATM系統(tǒng)程序的完整代碼
這篇文章主要介紹了C語言實(shí)現(xiàn)ATM系統(tǒng)程序的完整代碼,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-05-05
C++中回調(diào)函數(shù)(CallBack)的用法分析
這篇文章主要介紹了C++中回調(diào)函數(shù)(CallBack)的用法,較為詳細(xì)的分析了C++中回調(diào)函數(shù)(CallBack)的原理并以實(shí)例形式總結(jié)了其具體用法,具有一定參考借鑒價值,需要的朋友可以參考下2015-01-01
本文主要介紹了C++11中互斥鎖的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
C語言這門課程在計算機(jī)的基礎(chǔ)教學(xué)中一直占有比較重要的地位，然而要想突破C語言的學(xué)習(xí)，對指針的掌握是非常重要的，本文將具體針對指針的基礎(chǔ)做詳盡的介紹2022-06-06