首页 > 其他分享 >1759D(数位变0)

1759D(数位变0)

时间:2022-11-19 11:11:29浏览次数:71  
标签:int res ll cnt5 while 1759D define 数位

题目链接

题目大意:

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

  1. 是n的整数倍,且倍数小于m。
  2. 你应该使其末尾的0尽可能的多(如100后面有2个零,1020后面有一个零,我们应该输出100),在相同的情况下应该保证其最大化。
  3. 如果不能找到末尾有零的数就输出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 不要在一个地方死磕
 */

 

标签:int,res,ll,cnt5,while,1759D,define,数位
From: https://www.cnblogs.com/msluli/p/16905666.html

相关文章

  • Js保留到小数点后有数位、decimal有效数位
    链接:https://blog.csdn.net/a772116804/article/details/125916129  假设1w我们需要除以1亿10010/100000000 ≈ 0.0001 constdecimalFn=(num)=>{......
  • 数位DP
    通常问法:区间[l,r]的数中,满足某一条件数的个数。技巧1:[x,y]中满足情况的个数位f[y]-f[x-1]技巧2:从树的角度考虑问题例题1:度的数量题意:寻找[L,R]之间满足,是K个互不相等......
  • C++ 输出 控制小数位数
    头文件:#include<iomanip>按有效位输出是setprecision,按小数位数输出也是setprecision,但到底是谁取决于fixed。cout<<resetiosflags(ios::fixed)<<setprecision(n)......
  • 数位dp二则
    MagicNumbers CodeForces-628D题意:求区间[l,r]间偶数位都是d,奇数位都不是d的个数。l和r位数相等。解:l和r位数相等,很舒服,不用判前导0了。记录一下位数,判断其位置和......
  • 数位dp例题
    怎么感觉这种dp有点过于板子 1. 某人命名了一种不降数,这种数字必须满足从左到右各位数字成小于等于的关系,如12245 问区间【l,r】内有多少个不降数。#include<ios......
  • 如何用一个宏将一个数字的奇数位和偶数位交换
          如何用一个宏将一个数字的奇数位和偶数位交换呢?eg:    比如9,它的十进制应该是 1001 改变后应该是0110,也就是6。       首先,我们应该思考怎么得......
  • 【XSY4186】Binomial(结论,数位DP)
    题面Binomial题解设\(\operatorname{ord}(n)\)表示\(n\)分解质因数后\(p\)的幂次,那么我们就是对于每一个\(k\)要求有多少\(0\leqm\leqn\)使得\(\operatorn......
  • 游戏主要是这样的,计算正整数 n 每个数位上的数之积,例如 24,它的每个数位上的数字之积为
    publicstaticvoidmain(String[]args){ Scannerinput=newScanner(System.in); System.out.println("请输入一个正整数:"); intnum=input.nextInt(); intc=getN......
  • 一本通数位DP小结(更新中)
    「一本通5.3例1」AmountofDegrees点击查看代码//先转化为前缀和//从头到尾枚举每一位:这一位的贡献为前面的位都相同,这一位比原来更小,后面的位任意的方案......
  • Python:浮点数保留小数位数的方法整理
    示例print('%.2f'%1.255)#1.25print('{:.2f}'.format(1.2635))#1.26print(format(1.235,'.2f'))#1.24print(round(1.23456,2))#1.23参考Python保留......