题解：P17413 「IXOI R3」时间复杂度分析

Sunrise_up · 2026-09-06 17:42:39 · 题解

求点赞 qwq！

思路

就是模拟：

• 若 n^2\le 5\times 10^8，输出 O(n^2)。
• 否则若 n\le 5\times 10^8，输出 O(n)。
• 否则输出 O(1)。

但是发现 n^2 可能会爆 long long。

为了避免考虑更多情况，我们可以使用 __int128。

有符号 __int128 的范围是 -2^{127}\sim 2^{127}-1。

但是 __int128 类型的变量不可以读入，这个要注意一下。

或者不用 __int128，发现 n^2\le 5\times 10^8 当且仅当 n\le \sqrt{5\times 10^8}，由于 n 为整数，那么 n\le 22360。

代码

时间复杂度 O(1)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
__int128 _,x=5e8;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n,_=n;
    if(_*_<=x)cout<<"O(n^2)";
    else if(_<=x)cout<<"O(n)";
    else cout<<"O(1)";
}