FOJ 1607 Greedy division 数学题 - c++编程基础

给定一个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    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
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;isqrt(N*1.0)) continue;//防止越界   
            for(j=i*i;j1)  
    {  
        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 





#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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;isqrt(N*1.0)) continue;//防止越界
            for(j=i*i;j1)
    {
        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;
}