BUPT2017 wintertraining(15) #8E
题意
长度为n（\(n<2^{63}\)）的绳子，每隔长度L（1<L<n）做一次标记，标记值就是L，L是n的约数。
每轮标记都选一个L，且L之间两两互质。
求L的最多种数K。以及标记之和S的最大值。
题解
对n进行分解质因数，K就是不同质因子的个数，S就是p^{a_i}之和。不过题目要求L<n，所以当S算出来是n时，再除以一下最小的质因子。
分解比较小的n(<1e9)，可以直接枚举，复杂度是\(O(\sqrt n)\)。但是这里n比较大，需要用更高效的算法。
官方标程的方法：
先用Miller Rabin素数测试判断n是否是素数，是则直接返回。否则用pollard_rho算法找出用一个因子p。再递归地分解p和n/p。
代码
#include <cstdio>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
const int Times=10;
ll gcd(ll a, ll b){
while(b){
ll t=a%b;
a=b;
b=t;
}
return a;
}
ll qmul(ll a, ll b, ll m){
ll ans=0;
while(b){
if(b&1){
ans=ans+a;
if(ans>=m)ans-=m;
}
a<<=1;
if(a>=m)a-=m;
b>>=1;
}
return ans;
}
ll qpow(ll a, ll b, ll m){
ll ans=1;
while(b){
if(b&1)
ans=qmul(ans,a,m);
a=qmul(a,a,m);
b>>=1;
}
return ans;
}
bool Miller_Rabin(ll n){
if(n==2)return true;
if(n<2||!(n&1))return false;
ll m=n-1,x,y,a;
int k=0;
while(!(m&1)){
++k;
m>>=1;
}
for(int i=0;i<Times;++i){
a=rand()%(n-1)+1;
x=qpow(a,m,n);
for(int j=0;j<k;++j){
y=qmul(x,x,n);
if(y==1&&x!=1&&x!=n-1)return false;
x=y;
}
if(y!=1)return false;
}
return true;
}
ll pollard_rho(ll n, ll c){
ll i=1, k=2, x, y;
x=y=rand()%(n-1)+1;
while(1){
++i;
x=(qmul(x, x, n)+c)%n;
ll d=gcd((y-x+n)%n, n);
if(d>1&&d!=n)return d;
if(y==x)return n;
if(i==k){
y=x;
k<<=1;
}
}
}
ll fac[200],cnt;
void find(ll n,int c){
if(n==1)return;
if(Miller_Rabin(n)){
fac[++cnt]=n;
return;
}
ll p=n;
ll k=c;
while(p>=n)p=pollard_rho(p,c--);
find(p,k);
find(n/p, k);
}
int main(){
int t;ll n;
scanf("%d", &t);
while(t--){
cnt=0;
scanf("%lld", &n);
find(n, 97);
sort(fac, fac+cnt+1);
int num=0;
ll sum=0,tmp=0;
for(int i=1;i<=cnt;++i){
if(fac[i]!=fac[i-1]){
++num;
sum+=tmp;
tmp=fac[i];
}else tmp*=fac[i];
}
if(num==1)sum=n/fac[1];
else sum+=tmp;
printf("%d %lld\n",num, sum);
}
return 0;
}