还是超时问题

player-none

不好意思，最后发现是范围出了问题，int 改longlong p<=n改成p*p<=n就解决了

草烦死了题目里有不可见字符

题目描述
给定一个正整数k，有k次询问，每次给定三个正整数ni,ei,di，求两个正整数pi,qi，使ni=pi×qi、ei×di=(pi-1)(qi-1)+1。
输入描述
第一行一个正整数k，表示有$k$次询问。
接下来k行，第i行三个正整数$ni,di,ei$。
输出描述
输出k行，每行两个正整数$pi,qi$表示答案。
为使输出统一，你应当保证$pi≤qi$。
如果无解，请输出$NO$

样例1
输入
10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109
输出
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示
以下记$m=n&#8722;e×d+2$。
保证对于100%的数据，1≤k≤10^5，对于任意的1≤i≤k，1≤ni&#8203;≤10^18，1≤ei&#8203;×di&#8203;≤10^18，1≤m≤10^9。

我的代码：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.     int k;
   
5.     cin>>k;
   
6.     for(int i=0;i<k;i++){
   
7.         int n,e,d;
   
8.         cin>>n>>e>>d;
   
9.         int ed=e*d;
   
10.         bool solve=false;
    
11.         for(int p=1;p<=n;p++){
    
12.             if(n%p)continue;
    
13.             int q=n/p;
    
14.             if(n-p-q+2==ed){
    
15.                 cout<<p<<" "<<q<<"\n";
    
16.                 solve=true;
    
17.                 break;
    
18.             }
    
19.         }
    
20.         if(!solve){
    
21.             cout<<"NO\n";
    
22.         }
    
23.     }
    
24.     return 0;
    
25. }

复制代码

还是最后两空过不了



修改后：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.     int k;
   
5.     cin>>k;
   
6.     for(int i=0;i<k;i++){
   
7.         long long n,e,d;
   
8.         cin>>n>>e>>d;
   
9.         long long ed=e*d;
   
10.         bool solve=false;
    
11.         for(long long p=1;p*p<=n;p++){
    
12.             if(n%p)continue;
    
13.             long long q=n/p;
    
14.             if(n-p-q+2==ed){
    
15.                 cout<<p<<" "<<q<<"\n";
    
16.                 solve=true;
    
17.                 break;
    
18.             }
    
19.         }
    
20.         if(!solve){
    
21.             cout<<"NO\n";
    
22.         }
    
23.     }
    
24.     return 0;
    
25. }

复制代码

FishC

你的代码可能超时的原因是暴力枚举$p$的方式过于低效。我们可以利用数学方法优化求解过程。

### **优化思路**
1. **推导$p$的范围**  
   由题目条件：
   \[
   e \times d = (p-1) \times (q-1) + 1
   \]
   变形得：
   \[
   (p-1) \times (q-1) = e \times d - 1
   \]
   设$m = n - e \times d + 2$，则：
   \[
   p \times q = n
   \]
   \[
   (p-1) \times (q-1) = e \times d - 1
   \]
   由此可知，$p$和$q$是$n$的两个因子，且满足上述方程。

2. **优化因子分解**  
   由于$n$的范围可达$10^{18}$，直接暴力枚举$p$的方式不可行。我们可以：
   - **只枚举$n$的因子**，减少搜索空间。
   - **利用$m$的范围（$m \leq 10^9$）**，减少不必要的计算。

### **优化代码**

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. void solve() {
   
6.     long long n, e, d;
   
7.     cin >> n >> e >> d;
   
8.     long long ed = e * d;
   
9.     long long m = n - ed + 2;
   
10. 
    
11.     if (m <= 0) {
    
12.         cout << "NO
    
13. ";
    
14.         return;
    
15.     }
    
16. 
    
17.     bool found = false;
    
18.     for (long long p = 1; p * p <= n; ++p) {
    
19.         if (n % p == 0) {
    
20.             long long q = n / p;
    
21.             if ((p - 1) * (q - 1) == ed - 1) {
    
22.                 cout << min(p, q) << " " << max(p, q) << "
    
23. ";
    
24.                 found = true;
    
25.                 break;
    
26.             }
    
27.         }
    
28.     }
    
29. 
    
30.     if (!found) {
    
31.         cout << "NO
    
32. ";
    
33.     }
    
34. }
    
35. 
    
36. int main() {
    
37.     ios::sync_with_stdio(false);
    
38.     cin.tie(nullptr);
    
39. 
    
40.     int k;
    
41.     cin >> k;
    
42.     while (k--) {
    
43.         solve();
    
44.     }
    
45. 
    
46.     return 0;
    
47. }

复制代码

### **优化点**
1. **只枚举$n$的因子**，减少循环次数。
2. **使用`ios::sync_with_stdio(false);`加速输入输出**，避免`cin`的性能瓶颈。
3. **提前判断$m$的范围**，如果$m \leq 0$，直接输出`NO`，减少不必要的计算。

### **时间复杂度**
- 由于$n$最多$10^{18}$，其因子最多约$10^9$，所以最坏情况下的复杂度约为$O(\sqrt{n})$，远优于暴力枚举$p$的$O(n)$。

这样优化后，代码应该能在合理时间内通过所有测试用例。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

player-none

sfqxx 发表于 2025-3-16 13:22
你这题目哪来的？

try this:

gesp三级真题,抱歉自己发现问题了，改了类型，p<=n改成p*p<=n就解决了

sfqxx

player-none 发表于 2025-3-16 13:23
gesp三级真题,抱歉自己发现问题了，改了类型，p