Submission #71012828

---

Source Code Expand

/*
*            /$$           /$$
*           |__/          |__/
*  /$$$$$$$$ /$$ /$$$$$$$$ /$$  /$$$$$$
* |____ /$$/| $$|____ /$$/| $$ /$$__  $$
*    /$$$$/ | $$   /$$$$/ | $$| $$  \ $$
*   /$$__/  | $$  /$$__/  | $$| $$  | $$
*  /$$$$$$$$| $$ /$$$$$$$$| $$|  $$$$$$$
* |________/|__/|________/|__/ \____  $$
*                                   | $$
*                                   | $$
*                                   |__/
*/
//hj23308±£ÓÓÎÒ
//Missile±£ÓÓÎÒ
/*
* ÐÑÁËÔÚÃÎÀïÕõÔú£¬²»¾õ÷öµ­Á˳¯Ï¼
*/
/*
* ÎҺܸßÐËÄãûÓÐÍüÁËÎÒ£¬µ«ÊÇÎÒÏÖÔÚ¸üÏ£ÍûÄãÒѾ­ÍüÁËÎÒÁË¡£
* Ï£ÍûÔÚÄãµÄ¼ÇÒäÖУ¬ÎÒÖ»Êdz¾ÍÁÒ»´é£¬´ÓÄãµÄÈ«ÊÀ½ç·¹ý£¬È»ºóËÄÉ¢·ÉÑï²»ÁôÏÂÒ»µãºÛ¼££¬¶øÄãÒª²»»ØÍ·µÄÍùÇ°×ß¡£
* ÎÒ¸üÏ£ÍûÎÒÖ»ÊÇ´ÓÄãµÄÈ«ÊÀ½ç·¹ý£¬Ö»ÊÇ·¹ý
*/
/*
* Ö»ÊÇÎÒÔÚÊ®×Ö·¿ÚÊØÁËÌ«¾Ã£¬Êص½»ÆɳÈçÓêÑÚÂñÒ»Çкۼ££¬²Å·¢ÏÖ×Ô¼ºµÈµÄÈËÒѾ­À뿪ÁË¡£
*/
/*
* ÌýÎÒµÄ ±ð»ØÍ· »ØÍ·¾Í¿ÉÄÜ»áÀáÁ÷ÂúÃ棬»á±»»ÆɳÑÚÂñ£¬ËùÒÔ¼´Ê¹Í´¿àÒ²ÒªÏòÇ°×ß
*/
/*
* ÎÒÌýµ½ÁË¡¸ÌìÐн¡¡¹µÄ»ØÏ죬ÕâÊÇÒ»¸öΰ´ó¶·Ê¿µÄ²»Ï¢×ÔÇ¿£»
* ÎÒÌýµ½ÁË¡¸ÆÆÍò·¨¡¹µÄ»ØÏ죬ÕâÊÇÒ»¸öºÚµÀ´òÊÖµÄÊØ»¤ÓûÍû£»
* ÎÒ¿´¼ûÁË¡¸ÉúÉú²»Ï¢¡¹µÄ¼¤µ´£¬ÕâÊÇÒ»¸öÆ­×ÓµÄΰ´óÀÖÕ£¡
*/
/*
* ÎÒÓÃÐé¼ÙµÄÃæ¾ßÕÕ¹Ë×ÅϸÄåµÄ¸ÐÇ飻
* ÎÒÒÔ»ªÀöµÄÒÂÎïϲØן¯ÀõÄѪÈ⣻
* µ±ÎÒÕªÏÂÃæ¾ß£¬ÍÊÈ¥ÒÂÎ¼´±ãÊÇÎÒ×îÇ×½üµÄÈË£¬Ò²ÎÞ·¨Ö±ÊÓÎÒ
*/
#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
mt19937 engine(chrono::steady_clock().now().time_since_epoch().count());
const int MAXN=2e5+5;
int t,n,m;
long long a[MAXN],num[MAXN];
struct Large {
	int N;
	long long sum[2*MAXN];
	void newN() {
		sum[++N]=0;
	}
	void init() {
		N=0;
	}
	void Add(int pos,long long val) {
//		cout<<"add : "<<pos<<" , "<<val<<"\n";
		while(N<pos) newN();
		long long res=0;
		for(int i=pos;val||res;i++) {
			if(N<i) newN();
			sum[i]+=res+val%10;
			res=0,val/=10;
			while(sum[i]>=10) sum[i]-=10,res++;
		}
	}
	void Cout() {
		bool flag=false;
		for(int i=N;i>=1;i--) {
			if(!flag&&sum[i]==0) continue;
			flag=true;
			cout<<sum[i];
		}
		if(!flag) cout<<"0";
		cout<<"\n";
	}
}number;
void Solve()
{
	number.init();
	for(int i=1;i<=n;i++) {
		num[i+1]+=num[i]/10;
	}
	long long res=0;
	for(int i=n;i>=1;i--) {
		res*=10;
		long long val=min(res,a[i]);
//		cout<<"res : "<<res<<"\n";
		a[i]-=val,num[i]-=res,res-=val;
//		cout<<i<<" : "<<num[i]<<"\n";
		long long sum=num[i]/m,oth=sum*m-a[i];
		number.Add(i,sum);
		res+=max(0ll,oth);
	}
	number.Cout();
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--) {
		cin>>n>>m;
		for(int i=1;i<=n;i++) {
			cin>>a[i];
			num[i]=a[i];
		}
		Solve();
	}
	return 0;
}

Submission Info

Judge Result