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

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

Problem - D - Codeforces

题意：

4fc4b272648e463b88fd5aba2c4d8ff5.png

思路：

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

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

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

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

最后再*10到不能乘为止

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

Code：

  1. #include <bits/stdc++.h>
  3. #define int long long
  5. using namespace std;
  7. using i64 = long long;
  9. const int mxn=1e2+10;
  11. int N,n,m;
  13. void solve(){
  14.     cin>>n>>m;
  15.     N=n;
  16.     int cnt2=0,cnt5=0;
  17.     while(n%2==0){
  18.         n/=2;
  19.         cnt2++;
  20.     }
  21.     while(n%5==0){
  22.         n/=5;
  23.         cnt5++;
  24.     }
  25.     //cout<<cnt2<<" "<<cnt5<<'\n'; 
  26.     int d=1ll;
  27.     while(cnt2<cnt5&&d*2<=m) d*=2,cnt2++;
  28.     while(cnt5<cnt2&&d*5<=m) d*=5,cnt5++;
  29.     while(d*10<=m) d*=10;
  30.     int t=m/d;
  31.     d*=t;
  32.     cout<<N*d<<'\n';
  33. }
  34. signed main(){
  35.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  36.     int __=1;cin>>__;
  37.     while(__--)solve();return 0;
  38. }

发表评论

表情：
评论列表 （有 0 条评论，162人围观）

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

相关阅读