【质因子】CF834 div2 D. Make It Round

傷城~ 2024-03-22 10:23 39阅读 0赞

[Problem - D - Codeforces][]

题意：

![4fc4b272648e463b88fd5aba2c4d8ff5.png][]

思路：

首先是个常识：一个数末尾0的个数取决于\{2,5\}这一对的数量

那么考虑统计n的2和5的质因子数量，然后贪心

先把5这个质因子搞饱和了，因为\*2比较小

然后把2这个质因子搞饱和

最后再\*10到不能乘为止

因为要最接近m，因此最后还得乘m/d

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e2+10;
    
    int N,n,m;
    
    void solve(){
    	cin>>n>>m;
    	N=n;
    	int cnt2=0,cnt5=0;
    	while(n%2==0){
    		n/=2;
    		cnt2++;
    	}
    	while(n%5==0){
    		n/=5;
    		cnt5++;
    	}
    	//cout<<cnt2<<" "<<cnt5<<'\n'; 
    	int d=1ll;
    	while(cnt2<cnt5&&d*2<=m) d*=2,cnt2++;
    	while(cnt5<cnt2&&d*5<=m) d*=5,cnt5++;
    	while(d*10<=m) d*=10;
    	int t=m/d;
    	d*=t;
    	cout<<N*d<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1759/problem/D
[4fc4b272648e463b88fd5aba2c4d8ff5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/2623781c379648eeb0990c4d00e2a05e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，39人围观）

还没有评论，来说两句吧...

相关阅读

相关 Educational Codeforces Round 122 (Rated for Div. 2) D. Make Them Equal

[Problem - D - Codeforces][] 题意：给定三个数组a,b,c，其中a数组一开始为1，b和c数组是给定的。对于每次操作，都可以选定一个i，任选

约定不等于承诺〃/ 2024年03月31日 14:42/ 0 赞/ 64 阅读

相关 Codeforces Round #834 (Div. 3) D. Make It Round

[Problem - D - Codeforces][] ![1c21641e1301413ea5db4b38f928ab5a.png][] Code： incl

￡神魔★判官ぃ/ 2024年03月31日 13:51/ 0 赞/ 83 阅读

相关 CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) C. Make It Permutation

[Problems - Codeforces][] 题意： ![8339051d6f2741b5ab9a8b0135eedfbb.png][] ![9c592e44e36

r囧r小猫/ 2024年03月24日 12:57/ 0 赞/ 62 阅读

相关【*1700质因子分解】CF1538D

[Problem - D - Codeforces][] 题意：给定两个数a和b，每次操作可以在两个数中选一个数然后除它的一个因子，问你是否可以进行正好K次操作之后a和b

た入场券/ 2024年03月22日 20:16/ 0 赞/ 80 阅读

相关【质因子】CF834 div2 D. Make It Round

[Problem - D - Codeforces][] 题意： ![4fc4b272648e463b88fd5aba2c4d8ff5.png][] 思路：首先是个常

傷城~/ 2024年03月22日 10:23/ 0 赞/ 40 阅读

相关【朴素DP】CF834div3 E. The Humanoid

虽然是简单DP，但是不妨碍我不会 [Problem - E - Codeforces][] ![a8cd5785c72547d59250f8894080b693.png][

Myth丶恋晨/ 2024年03月22日 10:07/ 0 赞/ 55 阅读

相关 Codeforces Round #402 (Div. 2) （A-D）

[CF \402 div2][CF _402 div2] A题：数学。具体看代码吧。很容易明白的。 include<bits/stdc++.h> usi

客官°小女子只卖身不卖艺/ 2022年07月12日 15:16/ 0 赞/ 201 阅读

相关 cf round340 div2 F（莫队）

题目链接：[传送门][Link 1] E. XOR and Favorite Number time limit per test 4 seconds mem

旧城等待，/ 2022年06月13日 02:00/ 0 赞/ 202 阅读

相关 Codeforces 155D(分解质因子+预处理)

问题描述: By 2312 there were n Large Hadron Colliders in the inhabited part of the universe

梦里梦外;/ 2022年06月03日 06:42/ 0 赞/ 180 阅读

相关 D. Zero Quantity Maximization（CF： Codeforces Round #544 (Div. 3)）

题目描述： You are given two arrays aa and bb, each contains nn integers. You want to cre

墨蓝/ 2022年03月11日 16:50/ 0 赞/ 191 阅读