FOJ 1607 Greedy division 数学题

2014-11-23 23:21:21 · 作者: · 浏览: 3
给定一个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; }