是专门卡单 $\log$ (
by jerry3128 @ 2021-05-05 08:37:12
emmm 意思是说扩欧没救了？
by XLost @ 2021-05-05 08:38:56
这题 3e6 线对本身就过不了 0.5s 吧
by Warriors_Cat @ 2021-05-05 08:43:09
@[XLost](/user/182022) 是求前缀积逆元，在乘回去，即求逆元的次数不能是 n 次。
by jerry3128 @ 2021-05-05 08:43:54
@[SSerWarriors_Cat](/user/147999) 确实，不过我看题解里有人用扩欧卡常卡过了（算了，不卡了，我去写递推了）多谢
by XLost @ 2021-05-05 08:49:36
@[jerry3128](/user/27338) 好的，多谢指点
by XLost @ 2021-05-05 08:50:34
@[XLost](/user/182022) 扩欧能过
```cpp
#include<cstdio>
template <typename L> inline void Read(L &x){
char c;
while((c=getchar())<'0'||c>'9');
x=c^48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48);
}
template <typename L> void Write(L x){
if(x>9) Write(x/10);
putchar(x%10^48);
}
inline void exgcd(register int a,register int b,register int &x,register int &y){
if(!b){x=1;y=0;}
else{
exgcd(b,a%b,x,y);
register int k=x;
x=y;y=k-(a/b)*y;
}
}
int main(){
register int n,p,x,y;
Read(n);Read(p);
for(register int i=1;i<=n;++i){
exgcd(i,p,x,y);
Write(x<0?x+p:x);
std::putchar('\n');
}
return 0;
}
by 蓝__ @ 2021-05-05 08:54:02
26次卡常的教训
by 蓝__ @ 2021-05-05 08:54:48
What?
等一等扩欧的迭代版不会比递归版跑的还慢吧。。。我再试试（听别人说我那样写有什么乱七八糟的尾递归内联优化）
by XLost @ 2021-05-05 08:58:38
@[蓝__](/user/304504) 用了您的卡常方法，最后一个点还是 **T** :[评测记录](https://www.luogu.com.cn/record/50299964)
不过时间调到了550ms(开不开O2都一个样)
（不卡了不卡了去写递推
by XLost @ 2021-05-05 09:11:43