[整数分解+dfs] light oj 1341 Aladdin and the Flying Carpet

题意：给定两个数a、b.问有多少组x、y满足b<=x<y且x*y=a.

思路：

由于数比较大了，所以循环找约数的办法就会超时了。

那么其实每个整数都可以分解为几个素数的幂相乘，所以我们就用分解素因子的方法分解整数。

接着用这些素因子dfs判断就好了。

加上一些剪枝就OK了。

代码：

#include"cstdio"
#include"cstring"
#include"cmath"
#include"cstdlib"
#include"algorithm"
#include"iostream"
#include"map"
#include"queue"
#define ll long long
using namespace std;
#define MAXN 1000007
bool mark[MAXN];
int ss[MAXN],sscnt;
void ssb()
{
    sscnt=0;
    memset(mark,false,sizeof(mark));
    mark[0]=mark[1]=true;
    for(int i=2; i<=MAXN; i++)
    {
        if(!mark[i])
        {
            for(int j=i+i; j<=MAXN; j+=i) mark[j]=true;
            ss[sscnt++]=i;
        }
    }
    return ;
}
int syz[123],used[123];
ll n,m,lit;
ll ans;
void dfs(ll x,int tep,int len)
{
    if(x>lit) return ;  //算是一个剪枝
    if(x>=m) ans++;
    for(int i=tep; i<len; i++)
    {
        if(used[i])
        {
            if(x*syz[i]>lit) return ;
            used[i]--;
            dfs(x*syz[i],i,len);
            used[i]++;
        }
    }
    return ;
}
int main()
{
    ssb();
    int t,cas=1;
    cin>>t;
    while(t--)
    {
        int cnt=0;
        scanf("%lld%lld",&n,&m);
        lit=(ll)sqrt(n*1.0);
        if(m>lit)  //大于就不存在了
        {
            printf("Case %d: 0\n",cas++);
            continue;
        }
        ll x=n;
        for(int i=0; i<sscnt; i++)
        {
            if((ll)ss[i]*ss[i]>x) break;
            if(x%ss[i]==0)
            {
                int tep=0;
                while(x%ss[i]==0)
                {
                    tep++;
                    x/=ss[i];
                }
                syz[cnt]=ss[i];
                used[cnt++]=tep;
            }
        }
        if(x!=1)
        {
            syz[cnt]=x;
            used[cnt++]=1;
        }
        ans=0;
        dfs(1,0,cnt);
        if(lit*lit==n) ans--;  //正方形不可以
        printf("Case %d: %lld\n",cas++,ans);
    }
    return 0;
}

[整数分解+dfs] light oj 1341 Aladdin and the Flying Carpet

原文：http://blog.csdn.net/wdcjdtc/article/details/44653689