用地推AC过，只是想看一下别的作法。 exgcd的复杂度和gcd是相同的，最坏会到O(logmax(x,y))，但是普遍只有O(1)，试了一下: printf:80pts,#6：614ms; std::cout + 关闭后同步：80pts,#6:575ms fwrite快写：80pts,#6：550ms 想知道具体卡不卡的过去。 fwrite快写代码：

#include <cstdio>

namespace QuikIO{
    
    int p3;
    const int size = 1 << 14;
    char out[size];
    
    #define flush() (fwrite(out,1,p3,stdout),p3 = 0)
    #define putchar(ch) (p3 == size && flush(),out[p3++] = ch)
    class Flush{public:~Flush(){flush();}}_;
    
    void write(int x){
        
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
        
    }
    
    void print(int x,char end = '\n'){
        
        write(x);
        putchar(end);
        
    }
    
}using QuikIO::print;

void exgcd(int a,int b,int &x,int &y){
    
    if (b == 0){
        
        x = 1,y = 0;
        return;
        
    }
    exgcd(b,a % b,y,x);
    y -= a / b * x;
    
}

int inv(int a,int p){
    
    int x,y;
    
    exgcd(a,p,x,y);
    x = (x % p + p) % p;
    
    return x;
}

int main(){
    
    int n,p;
    
    scanf("%d%d",&n,&p);
    for (int i = 1;i <= n;i++) print(inv(i,p));
    
    return 0;
}