我改了一下我的代码，但还是只有 40 分。
代码：
```cpp
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
unordered_map<int, int> mp;
inline int quick_pow(int x, int p, int mod){
int ans = 1;
while (p){
if (p & 1) ans = (ll)ans * x % mod;
x = (ll)x * x % mod;
p >>= 1;
}
return ans;
}
inline int BSGS(int a, int b, int p){
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
int m = sqrt(p) + 1, x, y = 1, z;
mp.clear();
a %= p;
b %= p;
x = b;
z = quick_pow(a, m, p);
mp[x] = 0;
for (register int i = 1; i < m; i++){
x = (ll)x * a % p;
mp[x] = i;
}
for (register int i = 1; i <= m; i++){
y = (ll)y * z % p;
if (mp.count(y)){
return i * m - mp[y];
}
}
return -1;
}
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
void exgcd(int a, int b, int &x, int &y){
if (b == 0){
x = 1;
y = 0;
return;
}
exgcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
}
inline int inv(int a, int b){
int x, y;
exgcd(a, b, x, y);
return x;
}
inline int exBSGS(int a, int b, int p){
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
int x = 0, y = 1, t, ans;
a %= p;
b %= p;
while ((t = gcd(a, p)) != 1){
if (b % t != 0) return -1;
x++;
b /= t;
p /= t;
y = (ll)y * (a / t) % p;
if (b == y) return x;
}
ans = BSGS(a, (ll)b * inv(y, p) % p, p);
if (ans == -1) return -1;
return ans + x;
}
int main(){
while (true){
int a, p, b, ans;
cin >> a >> p >> b;
if (a == 0 && p == 0 && b == 0) break;
ans = exBSGS(a, b, p);
if (ans == -1){
cout << "No Solution" << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
```
by Leasier @ 2020-03-14 21:02:56
我又改了一下我的代码，但还是只有 40 分。
代码：
```cpp
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> mp;
inline ll quick_pow(ll x, ll p, ll mod){
ll ans = 1;
while (p){
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
return ans;
}
inline ll BSGS(ll a, ll b, ll p){
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
ll m = sqrt(p) + 1, x, y = 1, z;
mp.clear();
a %= p;
b %= p;
x = b;
z = quick_pow(a, m, p);
mp[x] = 0;
for (register ll i = 1; i < m; i++){
x = x * a % p;
mp[x] = i;
}
for (register ll i = 1; i <= m; i++){
y = y * z % p;
if (mp.count(y)){
return i * m - mp[y];
}
}
return -1;
}
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a % b);
}
void exgcd(ll a, ll b, ll &x, ll &y){
if (b == 0){
x = 1;
y = 0;
return;
}
exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
}
inline ll inv(ll a, ll b){
ll x, y;
exgcd(a, b, x, y);
return x;
}
inline ll exBSGS(ll a, ll b, ll p){
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
ll x = 0, y = 1, t, ans;
a %= p;
b %= p;
while ((t = gcd(a, p)) != 1){
if (b % t != 0) return -1;
x++;
b /= t;
p /= t;
y = y * (a / t) % p;
if (b == y) return x;
}
ans = BSGS(a, b * inv(y, p) % p, p);
if (ans == -1) return -1;
return ans + x;
}
int main(){
while (true){
int a, p, b;
ll ans;
cin >> a >> p >> b;
if (a == 0 && p == 0 && b == 0) break;
ans = exBSGS(a, b, p);
if (ans == -1){
cout << "No Solution" << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
```
by Leasier @ 2020-03-15 17:05:46
我再改了一下我的代码，但还是只有 40 分。
代码：
```cpp
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> mp;
inline ll quick_pow(ll x, ll p, ll mod){
ll ans = 1;
while (p){
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
return ans;
}
inline ll BSGS(ll a, ll b, ll p){
a %= p;
b %= p;
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
ll m = sqrt(p) + 1, x, y = 1, z;
mp.clear();
x = b;
z = quick_pow(a, m, p);
mp[x] = 0;
for (register ll i = 1; i < m; i++){
x = x * a % p;
mp[x] = i;
}
for (register ll i = 1; i <= m; i++){
y = y * z % p;
if (mp.count(y)){
return i * m - mp[y];
}
}
return -1;
}
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a % b);
}
void exgcd(ll a, ll b, ll &x, ll &y){
if (b == 0){
x = 1;
y = 0;
return;
}
exgcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
}
inline ll inv(ll a, ll b){
ll x, y;
exgcd(a, b, x, y);
return x;
}
inline ll exBSGS(ll a, ll b, ll p){
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
ll x = 0, y = 1, t, ans;
while ((t = gcd(a, p)) != 1){
if (b % t != 0) return -1;
x++;
b /= t;
p /= t;
y = y * (a / t) % p;
if (b == y) return x;
}
a %= p;
b %= p;
ans = BSGS(a, b * inv(y, p) % p, p);
if (ans == -1) return -1;
return ans + x;
}
int main(){
while (true){
int a, p, b;
ll ans;
cin >> a >> p >> b;
if (a == 0 && p == 0 && b == 0) break;
ans = exBSGS(a, b, p);
if (ans == -1){
cout << "No Solution" << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
```
by Leasier @ 2020-03-17 09:48:23
我又改了一下我的代码，但还是只有 40 分。
代码：
```cpp
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> mp;
inline ll quick_pow(ll x, ll p, ll mod){
ll ans = 1;
while (p){
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
return ans;
}
inline ll bsgs(ll a, ll b, ll p){
a %= p;
b %= p;
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
ll m = sqrt(p) + 1, x, y = 1, z;
mp.clear();
x = b;
z = quick_pow(a, m, p);
mp[x] = 0;
for (register ll i = 1; i < m; i++){
x = x * a % p;
mp[x] = i;
}
for (register ll i = 1; i <= m; i++){
y = y * z % p;
if (mp.count(y)){
return i * m - mp[y];
}
}
return -1;
}
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a % b);
}
inline ll exbsgs(ll a, ll b, ll p){
a %= p;
b %= p;
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
if (b == 0){
ll x = 0, y = 1, t;
while ((t = gcd(a, p)) != 1){
if (b % t != 0) return -1;
x++;
b /= t;
p /= t;
y = y * (a / t) % p;
if (b == y) return x;
}
return -1;
}
ll x = 0, y = 1, t, ans;
while ((t = gcd(a, p)) != 1){
if (b % t != 0) return -1;
x++;
b /= t;
p /= t;
y = y * (a / t) % p;
if (b == y) return x;
}
ans = bsgs(a, b, p);
if (ans == -1) return -1;
return ans + x;
}
int main(){
while (true){
int a, p, b;
ll ans;
cin >> a >> p >> b;
if (a == 0 && p == 0 && b == 0) break;
ans = exbsgs(a, b, p);
if (ans == -1){
cout << "No Solution" << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
```
by Leasier @ 2020-03-18 20:59:44