首页 > 其他 > 详细

F(X)

时间:2014-05-22 06:46:12      阅读:359      评论:0      收藏:0      [点我收藏+]
题目描述:


我们定义 F(x)是满足 x  mod(a*b) == 0这样的a,b的组数。现在给你一个n,你需要求出 F(n) 输入格式: 多组数据,每组第一行有一个整数n, 0 < n <= 10^11。 输出格式: 每组输出一行,满足条件的(a,b)对数

分析:从题目可以看出,所输入的X必须要同时整除a和b,那么我们求出X%a==0时的c=X/a,然后得出d=c/b。那么从这里可以看出,这时候的c和d都满足公式 x mod (c*d)==0,由此可得,c和d都是X的因子。由于n最大可达10^11次方,因此我们将a的范围设为1<=a<=sqrt(n)+1,循环的范围知识sqrt(n),由此可知,时间复杂度降了很多很多。最后我们求出这范围内的因子,去掉重复的因子,然后一个个枚举比较就可以得出最终个数。自己看代码吧!

代码:

#include<stdio.h>
#include<string.h>
#include<math.h>
long long arr[100000];
int main()
{
    long long n,a,b,temp,cnt,m;
    int i,j,k;
    while(scanf("%lld",&n)!=EOF)
    {
        i=0;cnt=0;
        memset(arr,0,sizeof(arr));
        m=sqrt(n)+1;
        for(a=1;a<m;a++)
        {
            temp=n%a;
            if(temp==0)
            {
                temp=n/a;
                arr[i]=a;
                i=i+1;
                if(a!=temp)  
                {
                    arr[i]=temp;
                    i=i+1; 
                }
            }
        }
        //printf("%d\n",i);
        for(j=0;j<i;j++)
        {
            //printf("%lld ",arr[j]);
            for(k=0;k<i;k++)// && arr[a]*arr[b]<=n
            {
                //printf("%ld*%ld:%ld\n",arr[a],arr[b],n%(arr[a]*arr[b]));
                if(n%(arr[j]*arr[k])==0)
                {
                   cnt=cnt+1;;    
                }
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}

F(X),布布扣,bubuko.com

F(X)

原文:http://blog.csdn.net/wingahi/article/details/26179599

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!