学习编程中的Ben 发表于 2023-8-12 17:08
这他妈样例有问题啊!!!
第一个样例
输入:
额
学习编程中的Ben 发表于 2023-8-12 17:08
这他妈样例有问题啊!!!
第一个样例
输入:
你确实的
zhangjinxuan 发表于 2023-8-12 17:36
额
第二个样例中 《9是质数》
tommyyu 发表于 2023-8-12 17:39
第二个样例中 《9是质数》
妈妈生的{:10_282:}
在吗？
sfqxx 发表于 2023-8-12 19:00
在吗？
《我在》
学习编程中的Ben 发表于 2023-8-12 17:08
这他妈样例有问题啊!!!
第一个样例
输入:
我开个悬赏？
sfqxx 发表于 2023-8-12 16:11
这道题是绿题还是蓝题 。还是黄题？
应该是蓝题……{:10_243:}
我们班第一名也没有做出来，全班都没有做出来{:10_277:}
明天请教请教老师{:10_256:}
zhangjinxuan 发表于 2023-8-14 18:18
应该是蓝题……
我们班第一名也没有做出来，全班都没有做出来
《嗯，有道理》
看看gpt-4行不行{:10_256:}
我感觉就暴力干就完了，它要a最小的那个，让a从小到大试，找到第一个就输出，不用考虑多解的问题
两手空空儿 发表于 2023-8-15 15:32
我感觉就暴力干就完了，它要a最小的那个，让a从小到大试，找到第一个就输出，不用考虑多解的问题
万一 a = b = 2, c 是一个很大的素数怎么办（例如接近 5e17 的一个质数）
因为你要判断 a,b,c 是否都为质数啊
zhangjinxuan 发表于 2023-8-15 15:42
万一 a = b = 2, c 是一个很大的素数怎么办（例如接近 5e17 的一个质数）
因为你要判断 a,b,c 是否都 ...
打表！！！
这题应该是考压缩一个数组的方法的{:10_256:}
tommyyu 发表于 2023-8-15 23:11
打表！！！
这题应该是考压缩一个数组的方法的
STD:枚 举
只要用上特殊的方法就可以实现了。
比如 miller rabin
zhangjinxuan 发表于 2023-8-15 15:42
万一 a = b = 2, c 是一个很大的素数怎么办（例如接近 5e17 的一个质数）
因为你要判断 a,b,c 是否都 ...
先把N以内的质数找出来，a和b从最小的质数开始，c从最大的质数开始，找到结果应该不会很慢
两手空空儿 发表于 2023-8-16 11:36
先把N以内的质数找出来，a和b从最小的质数开始，c从最大的质数开始，找到结果应该不会很慢
这种方法也会hack啊{:10_333:}
不对啊，根据唯一分解定理，只需要枚举 a, b 即可
那万一 b,c 都是大质数怎么办{:10_277:}
zhangjinxuan 发表于 2023-8-16 11:48
这种方法也会hack啊
不对啊，根据唯一分解定理，只需要枚举 a, b 即可
不会的呀，b * c 要小于N, 最差的情况就是b大，c小，b,c都大的情况是不可能发生的
两手空空儿 发表于 2023-8-17 12:12
不会的呀，b * c 要小于N, 最差的情况就是b大，c小，b,c都大的情况是不可能发生的
我给你造一个数据
zhangjinxuan 发表于 2023-8-17 12:14
我给你造一个数据
3 + 999999937 * 999999937， 就是把N值取到最大呗，这是反推的结果
正推，b从最小的开始试，很可能远到不了这个数字就已经出结果了，反正不用考虑多解
两手空空儿 发表于 2023-8-17 12:53
3 + 999999937 * 999999937， 就是把N值取到最大呗，这是反推的结果
正推，b从最小的开始试，很可能远到 ...
{:10_291:}
搞了一下，性能卡在找质数的部分了。。。。。。。。。。。。{:5_107:}
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main(void){
long long num;
long long i, j, k, location;
vector<long long> arr;
cout << "请输入一个偶数 N(12 <= N <= 10^18)：";
cin >> num;
// num = 8000000;
cout << num << endl;
for(i = 2; i < num; i++){
k = (long long)sqrt(i);
for(j = 2; j <= k; j++){
if(i % j == 0){
break;
}
}
if(k + 1 == j){
arr.push_back(i);
}
}
cout << "共找到" << arr.size() << "个质数" << endl;
// for(i = 0; i < arr.size(); i++){
// cout << arr << " ";
// }
for(i = 0; i < arr.size(); i++){
location = arr.size() / 2;
for(j = 0; j < arr.size(); j++){
for(k = location; k >= 0; k--){
if(num - arr == arr * arr){
cout << endl << "找到结果：" << num << " = " << arr << " + " << arr << " * " << arr << endl;
return 0;
}
if(num - arr > arr * arr){
location = k;
break;
}
}
}
}
cout << "没有找到合适的结果";
return 0;
}