1. 题目描述
求乘法逆元。
2. 基本思路
利用扩展gcd求逆元，模板题目。
3. 代码
/* 3609 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 #define LL long long void egcd(LL a, LL b, LL& g, LL& x, LL& y) {
if (!b) {
g = a;
x = ;
y = ;
} else {
egcd(b, a%b, g, y, x);
y -= a/b*x;
}
} int inv(LL a, LL n) {
LL g, x, y; egcd(a, n, g, x, y);
if (g != )
return -; return x%n== ? n:(x%n+n)%n;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t;
LL a, m;
LL ans; scanf("%d", &t);
while (t--) {
scanf("%lld%lld", &a, &m);
ans = inv(a, m);
if (ans == -) {
puts ("Not Exist");
} else {
printf("%lld\n", ans);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
4. 代码生成器
import sys
import string
from random import randint def GenData(fileName):
with open(fileName, "w") as fout:
t = 1000
fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(1, 1000)
m = randint(1, 1000)
fout.write("%d %d\n" % (n, m)) def MovData(srcFileName, desFileName):
with open(srcFileName, "r") as fin:
lines = fin.readlines()
with open(desFileName, "w") as fout:
fout.write("".join(lines)) def CompData():
print "comp"
srcFileName = "F:\Qt_prj\hdoj\data.out"
desFileName = "F:\workspace\cpp_hdoj\data.out"
srcLines = []
desLines = []
with open(srcFileName, "r") as fin:
srcLines = fin.readlines()
with open(desFileName, "r") as fin:
desLines = fin.readlines()
n = min(len(srcLines), len(desLines))-1
for i in xrange(n):
ans2 = int(desLines[i])
ans1 = int(srcLines[i])
if ans1 > ans2:
print "%d: wrong" % i if __name__ == "__main__":
srcFileName = "F:\Qt_prj\hdoj\data.in"
desFileName = "F:\workspace\cpp_hdoj\data.in"
GenData(srcFileName)
MovData(srcFileName, desFileName)