自己试着写了个 class。

class ex_Lucas
{
	public :
                long long n, m, p;
		inline long long pow(long long a, long long b, const long long p = LLONG_MAX)
		{
			long long ans = 1;
			while (b)
			{
				if (b & 1) ans = ans * a % p;
				a = a * a % p;
				b >>= 1;
			}
			return ans;
		}
		long long fac(const long long n, const long long p, const long long pk)
		{
			if (!n) return 1;
			long long ans = 1;
			for (int i = 1; i < pk; ++i) if (i % p) ans = ans * i % pk;
			ans = pow(ans, n / pk, pk);
			for (int i = 1; i <= n % pk; ++i) if (i % p) ans = ans * i % pk;
			return ans * fac(n / p, p, pk) % pk;
		}
		long long exgcd(const long long a, const long long b, long long &x, long long &y)
		{
			if (!b)
			{
				x = 1, y = 0;
				return a;
			}
			long long xx, yy, g = exgcd(b, a % b, xx, yy);
			x = yy;
			y = xx - a / b * yy;
			return g;
		}
		long long inv(const long long a, const long long p)
		{
			long long x, y;
			exgcd(a, p, x, y);
			return (x % p + p) % p;
		}
		long long C(const long long n, const long long m, const long long p, const long long pk)
		{
			if (n < m) 	return 0;
			long long f1 = fac(n, p, pk), f2 = fac(m, p, pk), f3 = fac(n - m, p, pk), cnt = 0;
			for (long long i = n; i; i /= p) cnt += i / p;
			for (long long i = m; i; i /= p) cnt -= i / p;
			for (long long i = n - m; i; i /= p) cnt -= i / p;
			return f1 * inv(f2, pk) % pk * inv(f3, pk) % pk * pow(p, cnt, pk) % pk;
		}
		long long a[1000010], c[1000010], cnt;
		inline long long CRT()
		{
			long long M = 1, ans = 0;
			for (int i = 0; i < cnt; ++i) M *= c[i];
			for (int i = 0; i < cnt; ++i) ans = (ans + a[i] * (M / c[i]) % M * inv(M / c[i], c[i]) % M) % M;
			return ans;
		}
		long long exlucas(const long long n, const long long m, long long p)
		{
			long long tmp = sqrt(p);
			for (int i = 2; p > 1 && i <= tmp; ++i)
			{
				long long tmp = 1;
				while (!(p % i)) {p /= i, tmp *= i;}
				if (tmp > 1) {a[cnt] = C(n, m, i, tmp), c[cnt++] = tmp;}
			}
			if (p > 1) {a[cnt] = C(n, m, p, p), c[cnt++] = p;}
			return CRT();
		}
};
int main()
{
     long long x, y, z;
     cin >> x >> y >> z;
     ex_Lucas A;//这步运行会死循环
     cout << A.exlucas(x, y, z);
     return 0;
}

求大佬指出问题（帮调更好）。