当前位置:网站首页>E. Singhal and numbers (prime factor decomposition)
E. Singhal and numbers (prime factor decomposition)
2022-07-05 20:23:00 【Dimple】
https://codeforces.com/gym/102767/problem/E
The question
Give a number n, You can choose less than n As a factor of N.
- If N Prime number , So the answer is A + X N A + \frac{X}{N} A+NX;
- If N Is the sum , So the answer is B + X N B + \frac{X}{N} B+NX;
- If N by 1, So the answer is C + X N C + \frac{X}{N} C+NX.
ask , What is the minimum answer ?
Ideas
To minimize the answer , Be sure to find the largest prime factor , The largest combining factor .
Prime factor decomposition finds the maximum prime factor ,O( n \sqrt{n} n).
In order to find the maximum composite number , Sure First find the maximum factor :n / Minimum prime factor .
- If the maximum factor is prime , It means that there is no maximum combining factor .
- Otherwise, the maximum factor is the maximum resultant factor .
Note that the factor in this question should be less than n, So we can make a special judgment first n In the case of prime numbers .
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;
}
边栏推荐
- Introduction to dead letter queue (two consumers, one producer)
- leetcode刷题:二叉树14(左叶子之和)
- c語言oj得pe,ACM入門之OJ~
- 银河证券在网上开户安全吗?
- .Net分布式事務及落地解决方案
- 【数字IC验证快速入门】8、数字IC中的典型电路及其对应的Verilog描述方法
- 2022北京眼睛健康用品展,护眼产品展,中国眼博会11月举办
- Mongodb/ document operation
- How to select the Block Editor? Impression notes verse, notation, flowus
- [quick start of Digital IC Verification] 6. Quick start of questasim (taking the design and verification of full adder as an example)
猜你喜欢
【刷题记录】1. 两数之和
Unity editor extended UI control
1、强化学习基础知识点
【数字IC验证快速入门】7、验证岗位中必备的数字电路基础知识(含常见面试题)
小程序页面导航
Leetcode brush questions: binary tree 11 (balanced binary tree)
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
Ros2 topic [01]: installing ros2 on win10
Mysql频繁操作出现锁表问题
Station B up builds the world's first pure red stone neural network, pornographic detection based on deep learning action recognition, Chen Tianqi's course progress of machine science compilation MLC,
随机推荐
资源道具化
Some problems encountered in cocos2d-x project summary
鸿蒙系统控制LED的实现方法之经典
C langue OJ obtenir PE, ACM démarrer OJ
Relationship between mongodb documents
Enter the parallel world
Mysql频繁操作出现锁表问题
leetcode刷题:二叉树10(完全二叉树的节点个数)
信息学奥赛一本通 1337:【例3-2】单词查找树 | 洛谷 P5755 [NOI2000] 单词查找树
. Net distributed transaction and landing solution
1、强化学习基础知识点
c語言oj得pe,ACM入門之OJ~
mongodb/文档操作
本季度干货导航 | 2022年Q2
sort和投影
14、Transformer--VIT TNT BETR
Oracle tablespace management
Informatics Olympiad 1337: [example 3-2] word search tree | Luogu p5755 [noi2000] word search tree
nprogress插件 进度条
- Oui. Net Distributed Transaction and Landing Solution