kuangbin专题十四 LightOJ 1341 分解质因数

本文主要是介绍kuangbin专题十四 LightOJ 1341 分解质因数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b,其中a不能是正方形的面积。
题解：
分解质因数的应用，有两个公式：
（1）一个整数ｎ可以表示为若干素数乘积：n = p1^a1 * p2^a2*…*pk^ak;
（2） n 的正因数的个数可以表示为： num = (a1+1)*(a2+1)…(ak+1);
又因为当你求出一条边的时候就相当于知道了另一条边，所以得出的正因数和还要除于2，最后再减去小于b的因数就可以了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int MAXN=1e6+7;
bool prime[MAXN];
int p[MAXN],m=0;
LL a,b;
void Prime()
{prime[0]=prime[1]=false,prime[2]=true;for(int i=3;i<MAXN;i++){if(i%2) prime[i]=true;else prime[i]=false;}for(int i=3;i<=sqrt(MAXN);i++){if(prime[i])for(int j=i+i;j<MAXN;j+=i)prime[j]=false;}for(int i=2;i<MAXN;i++)if(prime[i])p[m++]=i;
}
int main()
{Prime();int t,k=1;scanf("%d",&t); while(t--){scanf("%lld%lld",&a,&b);if(a<b*b){printf("Case %d: 0\n",k++);continue;}LL ans=1,x=a;for(int i=0;i<m&&p[i]<=a;i++){int num=0;while(a%p[i]==0){num++;a/=p[i];}ans*=(num+1);}if(a>1)ans*=2;ans/=2;for(int i=1;i<b;i++)if(x%i==0)ans--;printf("Case %d: %lld\n",k++,ans);}
}