鱼C论坛

 找回密码
 立即注册
楼主: zhangjinxuan

今天去考试,一道题目不会做,求助

[复制链接]
 楼主| 发表于 2023-8-12 17:36:52 | 显示全部楼层
学习编程中的Ben 发表于 2023-8-12 17:08
这他妈样例有问题啊!!!
第一个样例
输入:

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-12 17:39:40 | 显示全部楼层
学习编程中的Ben 发表于 2023-8-12 17:08
这他妈样例有问题啊!!!
第一个样例
输入:

你确实的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-12 17:39:45 | 显示全部楼层

第二个样例中 《9是质数》
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-12 17:47:03 | 显示全部楼层
tommyyu 发表于 2023-8-12 17:39
第二个样例中 《9是质数》

妈妈生的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-12 19:00:26 | 显示全部楼层
在吗?
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-8-14 18:16:45 | 显示全部楼层

《我在》
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-14 18:17:18 | 显示全部楼层
学习编程中的Ben 发表于 2023-8-12 17:08
这他妈样例有问题啊!!!
第一个样例
输入:

我开个悬赏?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-14 18:18:31 | 显示全部楼层
sfqxx 发表于 2023-8-12 16:11
这道题是绿题还是蓝题 。还是黄题?


应该是蓝题……

我们班第一名也没有做出来,全班都没有做出来

明天请教请教老师
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-14 18:20:35 | 显示全部楼层
zhangjinxuan 发表于 2023-8-14 18:18
应该是蓝题……

我们班第一名也没有做出来,全班都没有做出来

《嗯,有道理》

看看gpt-4行不行

评分

参与人数 1荣誉 +1 收起 理由
zhangjinxuan + 1 >_<

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-15 15:32:26 | 显示全部楼层
我感觉就暴力干就完了,它要a最小的那个,让a从小到大试,找到第一个就输出,不用考虑多解的问题
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-15 15:42:26 | 显示全部楼层
两手空空儿 发表于 2023-8-15 15:32
我感觉就暴力干就完了,它要a最小的那个,让a从小到大试,找到第一个就输出,不用考虑多解的问题

万一 a = b = 2, c 是一个很大的素数怎么办(例如接近 5e17 的一个质数)

因为你要判断 a,b,c 是否都为质数啊
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-15 23:11:15 | 显示全部楼层
zhangjinxuan 发表于 2023-8-15 15:42
万一 a = b = 2, c 是一个很大的素数怎么办(例如接近 5e17 的一个质数)

因为你要判断 a,b,c 是否都 ...

打表!!!

这题应该是考压缩一个数组的方法的
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-16 06:52:08 From FishC Mobile | 显示全部楼层
tommyyu 发表于 2023-8-15 23:11
打表!!!

这题应该是考压缩一个数组的方法的

STD:枚 举

只要用上特殊的方法就可以实现了。

比如 miller rabin
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-16 11:36:19 | 显示全部楼层
zhangjinxuan 发表于 2023-8-15 15:42
万一 a = b = 2, c 是一个很大的素数怎么办(例如接近 5e17 的一个质数)

因为你要判断 a,b,c 是否都 ...

先把N以内的质数找出来,a和b从最小的质数开始,c从最大的质数开始,找到结果应该不会很慢
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-16 11:48:55 | 显示全部楼层
两手空空儿 发表于 2023-8-16 11:36
先把N以内的质数找出来,a和b从最小的质数开始,c从最大的质数开始,找到结果应该不会很慢

这种方法也会hack啊

不对啊,根据唯一分解定理,只需要枚举 a, b 即可

那万一 b,c 都是大质数怎么办
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-17 12:12:17 | 显示全部楼层
zhangjinxuan 发表于 2023-8-16 11:48
这种方法也会hack啊

不对啊,根据唯一分解定理,只需要枚举 a, b 即可

不会的呀,b * c 要小于N, 最差的情况就是b大,c小,b,c都大的情况是不可能发生的

评分

参与人数 1荣誉 +1 收起 理由
zhangjinxuan + 1 3 + 999999937 * 999999937

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-17 12:14:03 | 显示全部楼层
两手空空儿 发表于 2023-8-17 12:12
不会的呀,b * c 要小于N, 最差的情况就是b大,c小,b,c都大的情况是不可能发生的

我给你造一个数据
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-17 12:53:43 | 显示全部楼层

3 + 999999937 * 999999937, 就是把N值取到最大呗,这是反推的结果
正推,b从最小的开始试,很可能远到不了这个数字就已经出结果了,反正不用考虑多解
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-17 13:07:17 | 显示全部楼层
两手空空儿 发表于 2023-8-17 12:53
3 + 999999937 * 999999937, 就是把N值取到最大呗,这是反推的结果
正推,b从最小的开始试,很可能远到 ...

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-20 12:37:03 | 显示全部楼层
搞了一下,性能卡在找质数的部分了。。。。。。。。。。。。
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>

  4. using namespace std;

  5. int main(void){
  6.         long long num;
  7.         long long i, j, k, location;
  8.         vector<long long> arr;
  9.        
  10.         cout << "请输入一个偶数 N(12 <= N <= 10^18):";
  11.         cin >> num;       
  12. //        num = 8000000;
  13.         cout << num << endl;
  14.         for(i = 2; i < num; i++){
  15.                 k = (long long)sqrt(i);
  16.                 for(j = 2; j <= k; j++){
  17.                         if(i % j == 0){
  18.                                 break;
  19.                         }
  20.                 }
  21.                 if(k + 1 == j){
  22.                         arr.push_back(i);                       
  23.                 }
  24.         }
  25.         cout << "共找到" << arr.size() << "个质数" << endl;
  26. //        for(i = 0; i < arr.size(); i++){
  27. //                cout << arr[i] << " ";
  28. //        }       

  29.         for(i = 0; i < arr.size(); i++){
  30.                 location = arr.size() / 2;
  31.                 for(j = 0; j < arr.size(); j++){
  32.                         for(k = location; k >= 0; k--){                               
  33.                                 if(num - arr[i] == arr[j] * arr[k]){
  34.                                         cout << endl << "找到结果:" << num << " = " << arr[i] << " + " << arr[j] << " * " << arr[k] << endl;
  35.                                         return 0;
  36.                                 }
  37.                                 if(num - arr[i] > arr[j] * arr[k]){       
  38.                                         location = k;                               
  39.                                         break;
  40.                                 }
  41.                         }                       
  42.                 }
  43.         }       
  44.        
  45.         cout << "没有找到合适的结果";
  46.         return 0;
  47. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-10 00:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表