当前位置:网站首页>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;
}
边栏推荐
- Leetcode(347)——前 K 个高频元素
- 2020 CCPC 威海 - A. Golden Spirit(思维),D. ABC Conjecture(大数分解 / 思维)
- Rainbow 5.7.1 supports docking with multiple public clouds and clusters for abnormal alarms
- 小程序代码的构成
- Informatics Olympiad 1338: [example 3-3] hospital setting | Luogu p1364 hospital setting
- Process file and directory names
- Zero cloud new UI design
- [quick start to digital IC Verification] 8. Typical circuits in digital ICs and their corresponding Verilog description methods
- 14、Transformer--VIT TNT BETR
- .Net分布式事務及落地解决方案
猜你喜欢
JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
Practical demonstration: how can the production research team efficiently build the requirements workflow?
鸿蒙os第四次学习
1. Strengthen learning basic knowledge points
ROS2专题【01】:win10上安装ROS2
Leetcode (695) - the largest area of an island
欢迎来战,赢取丰厚奖金:Code Golf 代码高尔夫挑战赛正式启动
2022北京眼睛健康用品展,护眼产品展,中国眼博会11月举办
CTF逆向基础
走入并行的世界
随机推荐
July 4, 2022 - July 10, 2022 (UE4 video tutorial MySQL)
[quick start of Digital IC Verification] 3. Introduction to the whole process of Digital IC Design
鸿蒙os第四次学习
[quick start of Digital IC Verification] 7. Basic knowledge of digital circuits necessary for verification positions (including common interview questions)
全国爱眼教育大会,2022第四届北京国际青少年眼健康产业展会
model方法
Notes on key vocabulary in the English original of the biography of jobs (12) [chapter ten & eleven]
Bzoj 3747 poi2015 kinoman segment tree
What is PyC file
MySql的root密码忘记该怎么找回
资源道具化
2022北京眼睛健康用品展,护眼产品展,中国眼博会11月举办
DP: tree DP
Informatics Olympiad 1340: [example 3-5] extended binary tree
什么是pyc文件
微信小程序正则表达式提取链接
ICTCLAS用的字Lucene4.9捆绑
Leetcode brush questions: binary tree 18 (largest binary tree)
E. Singhal and Numbers(质因数分解)
Scala basics [HelloWorld code parsing, variables and identifiers]