FOJ 1607 Greedy division 數學題

給定一個n，將n平均分成m份，問有幾種方法，每種方法中找出最大的數。思路：就是求n的因子數、先將每個數求出最小素因子、再將n的所有素因子數加1相乘。小結論：求一個數的所有因子數、先分解、n=(a^x)*(b^y)*(c^z),(a、b、c均為素數)，因子數=(x+1)*(y+1)*(z+1)-1。           AC代碼：輸入數據很多，開始用cin果斷超時了。

 
#include <iostream>   
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
#include <cfloat>   
using namespace std;  
  
typedef long long LL;  
const int N=1000005;  
const LL II=1000000007;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
int n,Min[N];//每一個數的最小質因數   
  
void MIN()  
{  
    int i,j;  
    for(i=2;i<N;i+=2)  
    {  
        Min[i]=2;  
        Min[i-1]=0;  
    }  
    for(i=3;i<N;i++)  
    {  
        if(Min[i]==0)  
        {  
            Min[i]=i;  
            if(i>sqrt(N*1.0)) continue;//防止越界   
            for(j=i*i;j<N;j+=i)  
                if(Min[j]==0)  
                    Min[j]=i;  
        }  
    }  
}  
  
void xiaohao()  
{  
    int i,j,p=n,sum=1;  
    while(p>1)  
    {  
        int cnt=1,k=Min[p];  
        while(p%k==0)  
        {  
            cnt++;  
            p/=k;  
        }  
        sum*=cnt;  
    }  
    printf("%d %d\n",sum-1,n/Min[n]);  
}  
  
int main()  
{  
    MIN();  
    while(scanf("%d",&n)!=EOF)  
    {  
        xiaohao();  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cfloat>
using namespace std;

typedef long long LL;
const int N=1000005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

int n,Min[N];//每一個數的最小質因數

void MIN()
{
    int i,j;
    for(i=2;i<N;i+=2)
    {
        Min[i]=2;
        Min[i-1]=0;
    }
    for(i=3;i<N;i++)
    {
        if(Min[i]==0)
        {
            Min[i]=i;
            if(i>sqrt(N*1.0)) continue;//防止越界
            for(j=i*i;j<N;j+=i)
                if(Min[j]==0)
                    Min[j]=i;
        }
    }
}

void xiaohao()
{
    int i,j,p=n,sum=1;
    while(p>1)
    {
        int cnt=1,k=Min[p];
        while(p%k==0)
        {
            cnt++;
            p/=k;
        }
        sum*=cnt;
    }
    printf("%d %d\n",sum-1,n/Min[n]);
}

int main()
{
    MIN();
    while(scanf("%d",&n)!=EOF)
    {
        xiaohao();
    }
    return 0;
}