Java 解法, 执行用时: 480ms, 内存消耗: 17580K, 提交时间: 2023-03-31 17:45:33

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.*;

public class Main
{
    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();
    public static BigInteger rho(BigInteger N)
    {
        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;
        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        }
        while((divisor.compareTo(ONE)) == 0);
        return divisor;
    }

    public static ArrayList<BigInteger>list;
    public static TreeSet<BigInteger>set;
    public static BigInteger[]big=new BigInteger[2];
    public static int cur=0;
    public static void factor(BigInteger N)
    {
//        list=new ArrayList<>();
        if (N.compareTo(ONE) == 0) return;
        if (N.isProbablePrime(20))
        {
            list.add(N);
            set.add(N);
            big[cur++]=N;
            return;
        }
        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext())
        {
            cur=0;
            big=new BigInteger[2];
            list=new ArrayList<>();
            set=new TreeSet<>();
            BigInteger e=sc.nextBigInteger();
            BigInteger n=sc.nextBigInteger();
            BigInteger c=sc.nextBigInteger();
            factor(n);
            BigInteger p=big[0];
            BigInteger q=big[1];
            BigInteger phi=(p.subtract(ONE).multiply(q.subtract(ONE)));
            BigInteger d=e.modInverse(phi);
            BigInteger ans=c.modPow(d,n);
            System.out.println(d+" "+ans);
        }
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 118ms, 内存消耗: 504K, 提交时间: 2020-06-11 20:49:44

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ull unsigned long long
#define ll long long
#define cll const long long
#define ld long double
using namespace std;
void exgcd(ll a,ll b,ll&x,ll&y){
    if(b==0)return (void)(x=1,y=0);
    return (void)(exgcd(b,a%b,y,x),y-=a/b*x);
}
ll ok(ll a,ll x,cll mod){
    ll tmp=(a*x-(ll)((ld)1.0*a/mod*x+1.0e-1)*mod);
    return tmp<0?tmp+mod:tmp;
    ll re=0;
    while(x){
        if(x&1)re=(re+a)%mod;
        a=(a+a)%mod,x>>=1;
    }
    return re;
}
ll power(ll a,ll x,cll mod){
    ll re=1;
    while(x){
        if(x&1)re=ok(re,a,mod);
        a=ok(a,a,mod),x>>=1;
    }
    return re;
}
int main(){
    ull n,m,tmp,stx;ll c;
    scanf("%llu %llu %lld",&c,&n,&m);
    for(tmp=2ull*sqrt(n);;++tmp){
        ull tx=tmp*tmp-n*4;stx=sqrt(tx)+0.5;
        if(stx*stx==tx&&(tmp-stx)%2==0)break;
    }
    ll phi=((ll)(tmp-stx)/2-1)*((ll)(tmp+stx)/2-1),x,y;
    if(phi>c)exgcd(phi,c,y,x);else exgcd(c,phi,x,y);
    x%=phi;if(x<0)x+=phi;
    printf("%lld %lld\n",x,power(m,x,n));
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 106ms, 内存消耗: 488K, 提交时间: 2019-04-09 19:21:31

#include<bits/stdc++.h>
using namespace std;
#define int long long
int e,N,n,c,d,x,y;
void exgcd(int a,int b,int &d,int &x,int &y)
{
	if(b==0){d=a;x=1;y=0;}
	else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int add(int a,int b,int mod)
{
	a+=b;
	if(a>=mod)a-=mod;
	return a;
}
int jia(int a,int b,int mod)
{
	int res=0;
	while(b)
	{
		if(b%2)res=add(res,a,mod);
		a=add(a,a,mod);
		b/=2;
	}
	return res;
}
inline int kuai(int a,int b,int mod)
{
	int res=1;
	while(b)
	{
		if(b%2)res=jia(res,a,mod);
		a=jia(a,a,mod);
		b/=2;
	}
	return res;
}
int pollard_rho(int n,int c)
{
	int x=rand()*rand()%(n-1)+1;
	int y=x;
	int i=1,k=2;
	while(true)
	{
		x=(jia(x,x,n)+c)%n;
		int d=__gcd((x-y+n)%n,n);
		if(d>1&&d<n)return d;
		if(x==y)return n;
		if(++i==k)
		{
			k=k*2;
			y=x;
		}
	}
}
signed main()
{
	srand(19260817);
	scanf("%lld%lld%lld",&e,&N,&c);
	int p=N;
	while(p>=N)p=pollard_rho(p,120);
	int r=(p-1)*(N/p-1);
	exgcd(e,r,d,x,y);
	x=(x%r+r)%r;
	printf("%lld %lld",x,kuai(c,x,N));
	return 0;
}