补题向 | Concatenated Multiples（map int和string转换）

Concatenated Multiples

给出n个数和k，两个数组合而成一个新数，这个新数能被k整除，有多少个这样的组合

假如数13和2，k为4，组合成132，对k求余，可以看成130%k+2%k，要知道132%k是不是等于k，相当于求k-（130%k）等不等于2

在上面例子里，13后面加一个0是由2的位数决定的

存在一种特殊情况，自己和自己组合可以被k整除

使用map<ll,int>mp[11] 记录位数为1-10，余数为first的数的个数

由于要使用位数，将数保存为字符串

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<fstream>
#include<math.h>
#include<stack>
#include<queue>
#include<bitset>
#include<utility>
#include<set>
#include<map>
#include<sstream>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const double eps=0.0000000000001;
const ll mod=998244353;
int n,k;
int y[200005];
string s[200005];
map<ll,int> mp[11];
int main(){
	while(~scanf("%d%d",&n,&k)){
		int a;
		for(int i=0;i<n;i++){
			scanf("%d",&a);
			stringstream ss;
			ss.clear();//清除上个输入内容，不然无法输入新数据 
			ss<<a;
			ss>>s[i];
			y[i]=a%k;
			
			
			map<ll,int>::iterator iter;
			iter=mp[s[i].length()].find(y[i]);
			if(iter!=mp[s[i].length()].end()){
				iter->second++;
			}
			else{
				mp[s[i].length()].insert(make_pair(y[i],1));
			}
			
		}
		ll ans=0;
		ll b=1;//倍数 
		ll yy;
		for(int i=0;i<n;i++){
			b=1;
			for(int j=1;j<=10;j++){
				b*=10;
				b%=k;//y[i]*b可能会超出longlong范围 
				yy=y[i]*b;
				yy%=k;
				yy=k-yy;
				yy%=k;//如果a%k==0，那么yy=a，所以再求一次余数，保证yy肯定是比k小的数 
				
				map<ll,int>::iterator iter;
				iter=mp[j].find(yy);
				if(iter!=mp[j].end()){
					ans+=iter->second;
					
					if(y[i]==yy&&j==s[i].length()){
						//自己组合能被k整除的情况 
						ans--;	
					}
					
				}
			}
			
		}
		printf("%I64d\n",ans);
		for(int i=1;i<=10;i++){
			mp[i].clear();
		}
	}	
	return 0;
}
           

#include<sstream>

int 转 string

int a;

stringstream ss;

string s;

ss<<a;

ss>>s;

string 转 int

int a;

stringstream ss;

string s;

ss<<s;

ss>>a;

stringstream使用总结https://blog.csdn.net/fanyun_01/article/details/66967710

map详解https://www.cnblogs.com/shijingjing07/p/5588578.html