Mark the Rope

Problem Description
Eric has a long rope whose length is N, now he wants to mark on the rope with different colors. The way he marks the rope is:
1. He will choose a color that hasn’t been used
2. He will choose a length L (N>L>1) and he defines the mark’s value equals L
3. From the head of the rope, after every L length, he marks on the rope (you can assume the mark’s length is 0 )
4. When he chooses the length L in step 2, he has made sure that if he marks with this length, the last mark will be at the tail of the rope
Eric is a curious boy, he want to choose K kinds of marks. Every two of the marks’ value are coprime(gcd(l1,l2)=1). Now Eric wants to know the max K. After he chooses the max K kinds of marks, he wants to know the max sum of these K kinds of marks’ values.
You can assume that Eric always can find at least one kind of length to mark on the rope.

Input
First line: a positive number T (T<=500) representing the number of test cases
2 to T+1 lines: every line has only a positive number N (N<263) representing the length of rope

Output
For every test case, you only need to output K and S separated with a space

Sample Input
2
180
198

Sample Output
3 18
3 22

https://blog.csdn.net/lethic/article/details/7842978

/*来自 http://www.cnblogs.com/flipped/p/7148231.html*/
#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;
}