本来想搬砖,无奈没砖可搬,DIY 吧,反正也花不了多长事件
BigInteger求欧拉函数:
public static BigInteger bigIntegerEuler(BigInteger n) { BigInteger ret = new BigInteger(n.toString()); BigInteger i = new BigInteger("2"); BigInteger one = new BigInteger("1"); BigInteger zero = new BigInteger("0"); for (; i.multiply(i).compareTo(n) <= 0; i.add(one)) { if (n.mod(i).compareTo(zero) == 0) { ret = ret.subtract(n.divide(i)); do { n = n.divide(i); }while (n.mod(i).compareTo(zero) == 0); } } if (n.compareTo(one) > 0) { ret = ret.subtract(ret.divide(n)); } return ret; }
参照代码:
ll euler(ll n) // ll 为 long long { ll ret=n; for(ll i=2;i*i<=n;i++){ if(n%i==0){ ret-=ret/i; while(n%i==0){ n/=i; } } } if(n>1)ret-=ret/n; return ret; }
生活依然苦涩.........................