[整数分解+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 longusing namespace std;#define MAXN 1000007bool 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;}

人生谁无少年时，甜苦酸辛各自知。