题意:给定两个数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