这题要求线性
by Coffee_zzz @ 2023-03-05 21:00:00
@[Stitch0711](/user/675466) 要求线性复杂度。
by RP_INT_MAX @ 2023-03-05 21:03:01
@[RP_INT_MAX](/user/566289) $p$ 才 $2$ 个亿，$O(\log p)$ 也就 $30$，乘一个 $3\times 10^6$ 也能过啊，你谷机子快。
by sto_5k_orz @ 2023-03-05 21:05:52
@[Stitch0711](/user/675466) 注意你用的是 $\operatorname{long long}$ 并且这题时限 $500\text{ms}$。
by AC_CSP @ 2023-03-05 21:08:57
@[AC_CSP](/user/481527) 换成了 $int$，开了 O2，快速幂还是 $64$
by sto_5k_orz @ 2023-03-05 21:11:53
@[Stitch0711](/user/675466) 换成了 $int$，exgcd 的做法 673ms，还是 TLE
by sto_5k_orz @ 2023-03-05 21:13:32
@[AC_CSP](/user/481527) @[RP_INT_MAX](/user/566289) 用线性做法 AC 了，谢谢！
by sto_5k_orz @ 2023-03-05 21:19:07
您的卡常也可以过
```cpp
#include<bits/stdc++.h>
using namespace std;
long long x, y;
char ob[1<<16];int os=0;
inline void flush(){fwrite_unlocked(ob,1,os,stdout),os=0;}
inline void pc(char x){ob[os++]=x;}
inline void wt(int x){
if(__builtin_expect(os>65504,0)){flush();}char st[12],*tp=st;
for(;x>9;x/=10){*tp++=(x%10)+48;}
pc(x+48);for(;tp!=st;){pc(*--tp);}pc('\n');
}
void exgcd(int a, int b) {
if(!b) {x = 1; y = 0; return ;}
exgcd(b, a % b); long long tx = x; x = y; y = tx - a / b * y;
}
int main() {
int n, p; cin >> n >> p;
for(int i = 1; i <= n; i++) {
exgcd(i, p);
int ans = x % p;
if(ans<0)ans+=p;
wt(ans);
}flush();
return 0;
}
```
by Killer_joke @ 2023-03-05 21:22:51