题目链接
题目大意
题目思路
这个题目的思路就是如果你求出a的逆元是b，那么你要求b的逆元的话，就直接是a了。所以你只要求出前
n
\sqrt n
n
左右的数。
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define fi first
#define se second
#define debug printf(" I am here\n");
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef pair
<int,int> pii
;
const ll INF
=0x3f3f3f3f3f3f3f3f;
const int maxn
=1e6+5,inf
=0x3f3f3f3f;
const double eps
=1e-10;
int mod
,inv
[maxn
];
signed main(){
int _
;scanf("%d",&_
);
while(_
--){
scanf("%d",&mod
);
inv
[0]=inv
[1]=1;
int mi
=inf
;
vector
<pii
> vec
;
for(int i
=2;i
<mod
;i
++){
inv
[i
]=1ll*(mod
-mod
/i
)*inv
[mod
%i
]%mod
;
if(inv
[i
]<=mi
){
if(i
>inv
[i
]) break;
mi
=inv
[i
];
vec
.push_back({i
,inv
[i
]});
}
}
vector
<pii
> ans
;
for(int i
=0;i
<vec
.size();i
++){
ans
.push_back(vec
[i
]);
}
reverse(vec
.begin(),vec
.end());
for(int i
=0;i
<vec
.size();i
++){
if(vec
[i
].se
==vec
[i
].fi
) continue;
ans
.push_back({vec
[i
].se
,vec
[i
].fi
});
}
printf("%d\n",ans
.size());
for(int i
=0;i
<ans
.size();i
++){
printf("%d %d\n",ans
[i
].fi
,ans
[i
].se
);
}
}
return 0;
}
