喜欢整除的磊哥

NC218580. 喜欢整除的磊哥

描述

我们设一个整数 $x$ 的长度为 $Len(x)$ ，这里的长度是指在 $10$ 进制情况下数位的个数。
现在磊哥给你一个长度为 $n$ 的非负整数 $a$ 和另外一个正整数 $b$ 。他很喜欢整除，所以他希望 $a$ 能够是 $b$ 的倍数( $0$ 倍也可以)。
用 $a_1a_2\cdots a_n$ 表示数字 $a$ 的每一位的数字，注意下标是从 $1$ 开始的。
你现在可以将 $a$ 的某一位上的数修改成另外一个数，最多可以修改 $Len(b)$ 次。
注意：无论是修改前还是修改后， $a$ 都可以有前导 $0$ 。

输入描述

第一行一个正整数，表示测试的组数。
接下来每组三行：
第一行一个正整数表示。
第二行一个整数表示的长度。
第三行一个整数表示。

输出描述

第一行一个正整数表示修改的次数。
接下来k行每行两个数,表示将的第位的数字修改为。
应该满足。
如果有多种答案，输出任意一种满足的即可。

示例1

输入:

输出:

说明:

$42$ 是 $2$ 的倍数( $21$ 倍)。

$0050471$ 是 $1231$ 的倍数( $41$ 倍)。

$00$ 是 $77283$ 的倍数( $0$ 倍)。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 130ms, 内存消耗: 11156K, 提交时间: 2021-03-28 01:26:43

#include<bits/stdc++.h>
#define int long long
const int N=1e6+10;
using namespace std;

char s[N];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,x,i;
		cin>>x>>n>>s+1;
		int sum=0;
		for(i=1;i<=n;i++)
			sum=(sum*10+s[i]-'0')%x;
		int k=0,a=x;
		while(a)
		{
			k++;
			a/=10;
		}
		int tot=0;
		for(i=max(1LL,n-k+1);i<=n;i++)
			tot=tot*10+s[i]-'0';
		int cha=(tot-sum+x)%x;
		cout<<min(k,n)<<endl; 
		for(i=1;i<=min(k,n);i++)
		{
			cout<<n-i+1<<" "<<cha%10<<endl;
			cha/=10;
		}
	} 	
	return 0;
}

上一题

下一题

详情