当前位置:网站首页>E. Singhal and Numbers(质因数分解)
E. Singhal and Numbers(质因数分解)
2022-07-05 20:08:00 【小酒窝.】
https://codeforces.com/gym/102767/problem/E
题意
给定一个数 n,可以选择小于 n 的因数作为 N。
- 如果 N 是质数,那么答案为 A + X N A + \frac{X}{N} A+NX;
- 如果 N 是合数,那么答案为 B + X N B + \frac{X}{N} B+NX;
- 如果 N 为1,那么答案为 C + X N C + \frac{X}{N} C+NX.
问,答案最小是多少?
思路
为了使答案最小,一定要找最大的质因数,最大的合因数。
质因数分解找到最大质数因子,O( n \sqrt{n} n).
为了找到最大的合数,可以先找到最大因数:n / 最小质因数。
- 如果最大因数是质数的话,说明其没有最大合因数。
- 否则最大因数就是最大合因数。
注意此题中因数要小于 n,所以可以先特判掉 n 是质数的情况。
Code
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a, b, c;
bool isPrim(int x){
if(x == 0 || x == 1) return 0;
for(int i=2;i<=x/i;i++)
{
if(x % i == 0) return 0;
}
return 1;
}
signed main(){
Ios;
cin >> T;
while(T--)
{
cin >> n;
cin >> a >> b >> c;
if(isPrim(n)){
cout << c + n << endl;
continue;
}
int mprim = -1, mcom = -1;
int minprim = -1;
int t = n;
for(int i=2;i<=t/i;i++)
{
if(t % i == 0)
{
while(t % i == 0) t/=i, mprim = i;
if(minprim == -1) minprim = i;
}
}
if(t != 1) mprim = t;
int min1 = 1e18, min2 = 1e18, min3 = 1e18;
min1 = a+n/mprim;
mcom = n/minprim;
if(!isPrim(mcom)) min2 = b+n/mcom;
min3 = c+n;
int ans = min(min(min1, min2), min3);
cout << ans << endl;
}
return 0;
}
边栏推荐
- 2022年7月4日-2022年7月10日(ue4视频教程mysql)
- How to select the Block Editor? Impression notes verse, notation, flowus
- Elk distributed log analysis system deployment (Huawei cloud)
- 2023年深圳市绿色低碳产业扶持计划申报指南
- Bzoj 3747 poi2015 kinoman segment tree
- JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
- Securerandom things | true and false random numbers
- 618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
- leetcode刷题:二叉树15(找树左下角的值)
- 解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
猜你喜欢
Elk distributed log analysis system deployment (Huawei cloud)
港股将迎“最牛十元店“,名创优品能借IPO突围?
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
[hard core dry goods] which company is better in data analysis? Choose pandas or SQL
Build your own website (16)
如何安全快速地从 Centos迁移到openEuler
Oracle-表空间管理
无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
How to select the Block Editor? Impression notes verse, notation, flowus
Leetcode brush question: binary tree 13 (the same tree)
随机推荐
微信小程序正则表达式提取链接
Leetcode brush question: binary tree 14 (sum of left leaves)
银河证券在网上开户安全吗?
Notes on key vocabulary in the English original of the biography of jobs (12) [chapter ten & eleven]
Database logic processing function
ByteDance dev better technology salon was successfully held, and we joined hands with Huatai to share our experience in improving the efficiency of web research and development
Some problems encountered in cocos2d-x project summary
Add data to excel small and medium-sized cases through poi
Leetcode brush questions: binary tree 18 (largest binary tree)
线程池参数及合理设置
计算lnx的一种方式
淺淺的談一下ThreadLocalInsecureRandom
【数字IC验证快速入门】6、Questasim 快速上手使用(以全加器设计与验证为例)
Redis cluster simulated message queue
期货如何网上开户?安不安全?
深度学习 卷积神经网络(CNN)基础
Gstreamer中的task
中金财富在网上开户安全吗?
[hard core dry goods] which company is better in data analysis? Choose pandas or SQL
Summer Challenge harmonyos - realize message notification function