题目描述
给定一个整数 n,执行如下算法:
如果 n=0,则结束算法。
找到 n 的最小质因子 d。
令 n 减去 d 并跳转步骤 1。
请你计算,在算法执行的过程中,一共进行了多少次减法操作。
输入格式
一个整数 n。
输出格式
一个整数,表示减法操作的次数。
数据范围
前三个测试点满足 2≤n≤5。
所有测试点满足 2≤n≤10^10。
样例
输入样例1:
5
输出样例1:
1
输入样例2:
4
输出样例2:
2
这一题,我在最后一分钟AC了!!!!!
可见这一题很doge啊哈哈
尤其是不让看测试数据qwq
那么,这条题目怎么做呢
不急,我们先来看代码^_^
算法1
时间复杂度:O(sqrt(n));
#include <bits/stdc++.h>
using namespace std;
//因为最小的素数是2,所以我们要向2的倍数靠拢
//输入的数有两种情况:奇数和偶数 ,所以我们要分情况
int main() {
unsigned long long n, s = 1;//因为数据卡到了10^10,所以要开unsigned long long(包括后面的循环变量也是的,我被这一点卡了两次啊啊啊!血的教训!)
cin >> n;
if (n % 2 != 0) {//如果是奇数 因为奇数-奇数=偶数(也就是能被2整除)所以用if就行了
for (unsigned long long j = 3; j * j <= n; j++) {//枚举,要开ull!(等价于 for (unsigned long long j = 3; j * j <= n; j+=2) )
if (n % j == 0) {//如果是因数
n -= j;//先减
cout << 1 + n / 2 << endl;//1是减的第一次(j),n/2同偶数的情况
return 0;//结束这个情况
}
}
cout << 1 << endl;//如果是素数,就是1次(除以它本身)
return 0;//结束这个情况
} else {//如果是偶数
cout << n / 2 << endl;//就是直接每次减2,要n/2次
return 0;//结束这个情况
}
return 0;//完美撒花
}
谢谢佬,懂了
呵呵没事的啦
%%%栓Q
#include[HTML_REMOVED]
using namespace std;
int main()
{
long long int x;
cin>>x;
if(x==2)
{
cout<<1;
return 0;
}
long long int ans=0,o=1;
while(x!=0)
{
int o=0;
for(int i=3;i<=x;i)
{
if(x%2==0)
{
x=x-2;
ans;
o=1;
break;
}
else if(x%i==0)
{
x=x-i;
ans++;
break;
}
}有问题吗
你这个MarkDown有点。。。
我看看
同学你重发一下,把MD格式搞对了,另外告诉我一下你是什么错qwq
点赞
谢谢
请问一下为什么我用longlong会超时啊
你把代码发一下
因该是算法问题
你先用ull试一下
咋又删了qwq
刚发现复制错了😂
az
int count(LL n) 把 int 改成 ull
for(int i=3;i*i<=n;i++) 把int 改成 ull
for(int i=3;ii<=n;i++) 改成for(ULL i=3;ii<=n;i+=2)
其他你再看看
okk,ull是比ll要更快吗
emm。。。
你超时 把 i++ 改成 i+=2
这应该是主要原因
啊呸
不是,搞错了qwq
我再看一下
好像是函数的int改成LL就没事了
明白啦,谢谢~
ull其实是更保险,防止超限了
没4,AC就好
ull似乎是无符号类型的long long,应该是更大,不会更快吧…