【题目来源】 https://www.luogu.com.cn/problem/P15798 【题目描述】 若 1/a 可化为一个有限的，不循环的小数，则称 a 为终止数。 请你求出在 L 到 R 中终止数的数量。 【输入格式】 输入一行，包含两个整数 L,R。 【输出格式】 输出一行，包含一个整数，表示 L 到 R 中终止数的数量。 【输入样例】 2 11 【输出样例】 5 【数据范围】 保证 1≤L≤R≤10^6。 【样例解释】 在 [2,11] 终止数有 2、4、5、8、10。 【算法分析】 ● 一个分数 p/q 在“最简形式”下，如果分母只包含质因子 2 和 5，则小数有限。如果分母包含其他质因子，则小数循环。例如，2/20=1/10=1/(2×5)，小数有限。3/18=1/6=1/(2×3)，小数循环。 ● 显然，问题可转化为统计区间 [le,ri] 中形如 2^x × 5^y 的数的个数。 ● 输出一个整数所有质因子的代码（https://blog.csdn.net/hnjzsyjyj/article/details/138091319）
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
for(int i=2; i<=sqrt(n); i++) { //Prime Factorization
while(n%i==0) {
cout<<i<<" ";
n/=i;
}
}
if(n>1) cout<<n;
return 0;
}
/*
in:180
out:2 2 3 3 5
in:12
out:2 2 3
*/
【算法代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
LL le,ri;
cin>>le>>ri;
int cnt=0;
for(LL i=1; i<=ri; i*=2) {
for(LL j=i; j<=ri; j*=5) {
if(j>=le && j<=ri) cnt++;
}
}
cout<<cnt;
return 0;
}
/*
in:2 11
out:5
*/
【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/138091319 https://mp.weixin.qq.com/s/B2fUqZ_1hRnSgc5z1unr_A
