题目来源：https://vjudge.net/problem/LightOJ-1341 【题意】 给出两个数a，b，问不小于b的因子乘积等于a的有多少组合。 【思路】 起初用sqrt（a）暴力了一发，TLE了，然后再一看，虽然a的范围是10^12把，但是T组数据的T却是4000，4000*1000000，，，不超时能行么。。。默默的鄙视下自己。 然后，另外一种方法就出来了，算术基本定理（来自百度百科）：任何一个大于1的自然数 ，都可以唯一分解成有限个质数的乘积 N=p1^a1*p2^a2….. ，这里 均为质数，其诸指数 是正整数。 一个大于1的正整数N，如果它的标准分解式为：N=p1^a1*p2^a2…..，那么它的正因数个数为 num=(1+a1)(1+a2)…. 而这道题，就可以使用这种方法，首先素数表要有，然后分解，记下个数，求出num，然后num/=2，就成了组合数量；然后减去1-b之间的可行因子组合，就得出了答案。 【代码】
#include<map> #include<stack> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<string> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int INF=1e9; typedef long long LL; const int maxn=1000000+10; int pri[maxn]; bool check[maxn]; int tot=0; void prime()//素数表 { mem(check,0); for(int i=2; i<maxn; i++) { if(!check[i]) { pri[tot++]=i; for(int j=i*2; j<maxn; j+=i) { check[j]=1; } } } } LL oper(LL x)//求num的操作 { LL ans=1; for(int i=0; i<tot&&x; i++) { if(pri[i]>x) break; int num=0; while(x%pri[i]==0) { num++; x/=pri[i]; } ans*=(1+num); } if(x>1) ans*=(1+1); return ans; } int main() { int T,cases=0; prime(); scanf("%d",&T); while(T--) { LL a,b; scanf("%lld%lld",&a,&b); if(a<=b*b)//特判 { printf("Case %d: 0\n",++cases); continue; } LL ans=oper(a); ans/=2; for(int i=1; i<b; i++) { if(a%i==0) ans--; } printf("Case %d: %lld\n",++cases,ans); } }