裸题

求\(ind_{n,a}b\)，也就是\(a^x \equiv b \pmod n\)

注意这里开根不能直接下取整

这个题少了一些特判也可以过...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

using namespace std;

typedef long long ll;

const double PI=acos(-1);

inline int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int a, b, n;

map<int, int> ma;

int Pow(ll a, int b, int p) {

	ll ans=1;

	for(; b; b>>=1, a=a*a%p)

		if(b&1) ans=ans*a%p;

	return ans;

}

int ind(int n, int a, int b) {

	int m=ceil(sqrt(n)+1e-8);

	ma.clear();

	int e=1;

	for(int i=0; i<m; i++) {

		if(!ma.count(e)) ma[e]=i;

		e=(ll)e*a%n;

	}

	e=Pow(e, n-2, n);

	for(int i=0; i<m; i++) {

		if(ma.count(b)) return i*m + ma[b];

		b=(ll)b*e%n;

	}

	return -1;

}

int main() {

	freopen("in","r",stdin);

	while(scanf("%d%d%d",&n,&a,&b)!=EOF) {

		int x = ind(n, a, b);

		if(x==-1) puts("no solution");

		else printf("%d\n",x);

	}

}