C++整数拼接技巧大揭秘

来自:网络
时间:2024-06-09
阅读:

问题描述:

给定一个长度为n的数组,A1,A2,...,An你可以从中选出两个数Ai和Aj(i≠j),然后将Ai和Aj一前一后拼成一个新的整数。例如12和345可以拼成12345或34512。注意交换Ai和Aj的顺序总是被视为两种拼法,即便Ai=Aj。请你计算有多少种拼法,满足拼出的整数就是k的倍数。

输入格式:

第一行包含两个整数n和k。

第二行包括n个整数A1,A2,...,An。

输出格式:

一个整数,代表答案。

例如输入:4 2

                 1 2 3 4

输出:6

规定:

对于30%的评测用例,1≤n≤1000,1≤K≤20,1≤Ai≤10^4

对于所有评测用例:1≤n≤10^5,1≤K≤10^5,1≤Ai≤10^9

分析:

拼接两个整数(如12和345),得到12×1000+345=12345或345*100+12=34512。因此可以得到一个数学等式:拼起来的值为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的值。

当确定Aj时就可以确定P,通过P的值与K的值,就可以通过Q=(K-P)%K得到Q的值。

结论:当确定Aj时,就可以确定Q和Aj的长度,此时只需要查看有多少个Ai可满足即可。

C++程序:

#include<iostream>
#include<string>
using namespace std;
typedef long long LL;
const int N=100010;
int s[11][N];//表示某个数*10^i%k==j的数量
int n;//表示将要输入的n个数
LL a[N];//存放n个数
int k;//表示k倍
LL res;//表示结果
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或自然语言举几个例子,方便弄懂! 

返回顶部
顶部