题目链接

题目大意：

给你两个整数n, m。你需要求一个数，它满足如下条件：

是n的整数倍，且倍数小于m。
你应该使其末尾的0尽可能的多（如100后面有2个零，1020后面有一个零，我们应该输出100），在相同的情况下应该保证其最大化。
如果不能找到末尾有零的数就输出n * m 即可。

解题思路：

这属于构造类型了吧，我们构造的目标是满足条件下的末尾0最多的数。那怎么构造呢？

我们可以发现一个规律：只有因子出现2和5才会出现一个0，两个的话会出现2个.......（你可能会抬杠5*6=30不是出现了吗？30是可以分解为一个5，和一个2的）。那么我们的目标就明确了，首先找到n里面的因子2和5的个数（当然要把后缀0先去了哈）

ll cnt2 = 0, cnt5 = 0;

int k = n;

while (k % 10 == 0) k /= 10; //去0

while (k % 2 == 0) cnt2 ++, k /= 2; //找2

while (k % 5 == 0) cnt5 ++, k /= 5; //找5

接下来就是匹配n的因子了，这里要先匹配5为保证最大化

ll res = 1;

	while (cnt5 > 0 && res * 2 <= m) //匹配5

	{

		cnt5 --, res *= 2;

	} 

	while (cnt2 > 0 && res * 5 <= m) //匹配2

	{

		cnt2 --, res *= 5;

	}

	while (res * 10 <= m) //匹配10

	{

		res *= 10;

	}

	int t = m / res; //为保证其结果最大化，在保证m是res倍数的前提下，让其变为其倍数。同时也可以包括无法求得有后缀0的情况

	if (t) res *= t;

AC代码：

#include<bits/stdc++.h>

#define ll long long

#define sz(a) ((int) (a).size())

#define vi vector< int >

#define me(a, x) memset(a, x, sizeof(a))

#define ull unsigned long long

#define PII pair<int, int>

using namespace std;

const int N = 1e6 + 10;

ll n, m;

void solved()

{

	cin >> n >> m;

	ll cnt2 = 0, cnt5 = 0;

	int k = n;

	while (k % 10 == 0) k /= 10; //去0

	while (k % 2 == 0) cnt2 ++, k /= 2; //找2

	while (k % 5 == 0) cnt5 ++, k /= 5; //找5 

	ll res = 1;

	while (cnt5 > 0 && res * 2 <= m) //匹配5

	{

		cnt5 --, res *= 2;

	} 

	while (cnt2 > 0 && res * 5 <= m) //匹配2

	{

		cnt2 --, res *= 5;

	}

	while (res * 10 <= m) //匹配10

	{

		res *= 10;

	}

	int t = m / res; //为保证其结果最大化，在保证m是res倍数的前提下，让其变为其倍数。同时也可以包括无法求得有后缀0的情况

	if (t) res *= t;

	cout << n * res << '\n';

}

int main(){

	ios :: sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	int t;

	cin >> t;

	while (t -- ) solved();

	return 0;

}

/* stuff you should look for 你应该寻找的东西

 * int overflow, array bounds (int)溢出，数组边界

 * special cases (n=1?) 特殊情况(n=1?)

 * do smth instead of nothing and stay organized 做一些事情而不是什么也不做，保证效率

 * WRITE STUFF DOWN 将东西写下

 * DON'T GET STUCK ON ONE APPROACH 不要在一个地方死磕

 */

巴特西

1759D(数位变0）

题目链接

题目大意：

解题思路：

AC代码：

最新文章

热门文章