本文主要是介绍LightOJ 1341 Aladdin and the Flying Carpet，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出整数 a 和 b ，求区间[b, a] 内的 a 的约数对的个数，a 的约数对（比如[2, 3] 与 [3, 2] 为同一对）。
分析：
这道题应用算数基本定理。
算数基本定理：
（1）一个大于1的正整数N，如果它的标准分解式为： 
，
那么它的正因数个数为 
。
（2） 它的全体正因数之和为 
。
当 
时就称N为完全数。 是否存在奇完全数，是一个至今未解决之猜想。
（3） 利用算术基本定理可以重新定义整数a和b的最大公因子 
和最小公倍数 
， 并证明 
。
（4）此外还可证明根号2是无理数等等。
（5）证明素数个数无限。
用到定理1（唯一分解定理）。求出正因数的个数，然后再除以2，便是对数的个数，最后再暴力求解出[1，b]中 a 的正因数个数，相减便是答案！
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;#define maxn 1000010
#define LL long long LL prim[maxn], p[maxn];
int k;
void find_prim()
{ k = 0; for(LL i = 2; i <= maxn; i++) { if(!p[i]) { prim[k++] = i; for(LL j = i+i; j <= maxn; j+=i) { p[j] = 1; } } }
}
LL cont(LL a)
{ LL s = 1; if(a == 0) { return 0; } LL tt = 0; LL i = 0; while(prim[i] < a && i < k) { tt = 0; if(a%prim[i] == 0) { while(a%prim[i] == 0) { a /= prim[i]; tt++; } } s *= tt+1; i++; } if(a > 1) { s *= 1+1;//一次 } return s;
}
int main()
{ LL a, b; int t; int kase = 1; find_prim(); scanf("%d",&t); while(t--) { scanf("%lld%lld", &a, &b); int cnt = 0; LL num = 0, ans; if(b >= sqrt(a)) ans = 0; // b大小限定 else { for(LL i = 1; i < b; i++) //暴力枚举[1, b]中a的约数 { if(a%i == 0) { cnt++; } } num = cont(a)/2; ans = num - cnt; } printf("Case %d: %lld\n", kase++, ans); } return 0;
}这篇关于LightOJ 1341 Aladdin and the Flying Carpet的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
