EOJ Monthly 2019.2 (based on February Selection) EOJ——3676 (思维+取模)

B. 解题

单测试点时限: 2.0 秒

内存限制: 1024 MB

“我把房门上锁,并非为了不让她进去,而是为了防止自己逃到她身边”。

她又被数学难住了。QQ 小方当然是不会对女生说”不”的。

她的数学题是这样的,她得到了一个十进制大整数,这个大整数只包含 1 - 9 这 9 个数字。

现在,要求选出其中连续的一段数字,把其他未被选中的数字全部变成 0,并且使得变换以后的大整数恰好是 m 的倍数。

QQ 小方为了表现自己的能力,所以一口答应给她写出在所有可能的数里面最小的一个。

但是她的问题太多了,她对于这一个大整数,需要对于 q 个不尽相同的 m 分别给出答案。

但是 QQ 小方自己不会。只能来求助你了,你能帮他解答吗?

输入

第一行包含一个大整数,这个整数的位数为 n (1≤n≤10^6)。

第二行一个整数 q (1≤q≤500) 代表询问次数。

对于每一个询问,包含一行一个整数,表示第 i 次询问的 mi (1≤mi≤5×10^7)。

保证 EOJ Monthly 2019.2 (based on February Selection)  EOJ——3676 (思维+取模)

输出

对于每一个询问输出两个整数 l,r 表示保留第 l 到第 r 位。保证一定有解。

样例

input

1249
4
7
3
2
83

output

3 4
4 4
3 3
2 4

提示

对于样例:
1249 这个数中,可选出的最小的7的倍数是49,最小的3的倍数是9,2的倍数是40,83的倍数是249。

题目粘贴过来有点变化,详细看原EOJ网站

题意:看提示就能懂~~

题解:就拿样例来说,1000=1249-249, 40=49-9,49=49-0 ......也就是说一个数都可以写成两个数的差,那么l令w=a-b,则w%m=0即:(a-b)%m=0,那么就是a%m=b%m.所以只需要找两个数模m相等就好了,注意b可以等于0,同时,因为抽屉原理,我们最多只要处理 m+1 个 a 就能找到答案,那么就可以写代码了,注意数据范围: 上代码:

#include <iostream>
using namespace std;
const int MAX = 1e7*5+100;//注意范围,别开小了,用题目中m的范围确定
int mp[MAX];
int main(){
	string s;
	cin >> s;
	int len=s.size();
	int p;
	cin >> p;
	while(p--){
		bool f=0;
		int x;
		scanf("%d",&x);
		int w=1;
		int ans=0;
		mp[0]=len;
		for (int i = len-1; i >= 0;i--){//倒着保证最小
			ans+=w*(s[i]-'0');//倒着求数
			w=(w*10)%x;//这里注意要模x,否则RT
			ans%=x;//推的式子
			if(mp[ans]){//标记是否模相等
				cout << i+1 << " " << mp[ans] << endl;//这里就是输出位置,因为从0开始,所以这样输出刚刚好
				f=1;
				break; 
			}
			mp[ans]=i;
		}
		if(f==0) cout << -1 << endl;
		for (int i = 0; i <= x+1;i++) mp[i]=0;//不能全部初始化,只把用到的初始化,否则T
	} 
	return 0;
} 

 

上一篇:js(vue)中json数据根据一个子节点递归查找所有父节点


下一篇:EOJ 2019.2月赛 D. 进制转换