player-none 发表于 2025-3-16 13:15:28

还是超时问题

本帖最后由 player-none 于 2025-3-16 13:23 编辑

不好意思，最后发现是范围出了问题，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−e×d+2$。
保证对于100%的数据，1≤k≤10^5，对于任意的1≤i≤k，1≤ni​≤10^18，1≤ei​×di​≤10^18，1≤m≤10^9。

我的代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
      int n,e,d;
      cin>>n>>e>>d;
      int ed=e*d;
      bool solve=false;
      for(int p=1;p<=n;p++){
            if(n%p)continue;
            int q=n/p;
            if(n-p-q+2==ed){
                cout<<p<<" "<<q<<"\n";
                solve=true;
                break;
            }
      }
      if(!solve){
            cout<<"NO\n";
      }
    }
    return 0;
}
还是最后两空过不了



修改后：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
      long long n,e,d;
      cin>>n>>e>>d;
      long long ed=e*d;
      bool solve=false;
      for(long long p=1;p*p<=n;p++){
            if(n%p)continue;
            long long q=n/p;
            if(n-p-q+2==ed){
                cout<<p<<" "<<q<<"\n";
                solve=true;
                break;
            }
      }
      if(!solve){
            cout<<"NO\n";
      }
    }
    return 0;
}

FishC 发表于 2025-3-16 13:15:51

你的代码可能超时的原因是暴力枚举$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$）**，减少不必要的计算。

### **优化代码**
#include <iostream>
#include <cmath>
using namespace std;

void solve() {
    long long n, e, d;
    cin >> n >> e >> d;
    long long ed = e * d;
    long long m = n - ed + 2;

    if (m <= 0) {
      cout << "NO
";
      return;
    }

    bool found = false;
    for (long long p = 1; p * p <= n; ++p) {
      if (n % p == 0) {
            long long q = n / p;
            if ((p - 1) * (q - 1) == ed - 1) {
                cout << min(p, q) << " " << max(p, q) << "
";
                found = true;
                break;
            }
      }
    }

    if (!found) {
      cout << "NO
";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    cin >> k;
    while (k--) {
      solve();
    }

    return 0;
}

### **优化点**
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 发表于 2025-3-16 13:23:04

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

try this:

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

sfqxx 发表于 2025-3-16 14:16:33

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

{:10_323:}
页: [1]
查看完整版本: 还是超时问题