题解 LightOJ1341 【Aladdin and the Flying Carpet】
xukuan
2020-11-05 10:48:48
题意：多组数据，每组数据输入$n,m$，求有多少组整数$(a,b)$满足$a*b=n$且$m \leq a \leq b$
其实是个小学奥数
先假设$m=0$，那么根据一个定理，$n=\prod_{i=1}^n p_i^{c_i}$，其中$p_i$为素数，$c_i$为正整数。那么$n$的因数个数为$\prod_{i=1}^n(c_i+1)$
然后我们看$n$的$<\sqrt n$的因数中有多少个$<m$的。
- 如果$m^2 \geq n$，说明无解
- 否则dfs找所有$<m$的因数
其实暴力也是可以的，因为$O(T\sqrt n) \leq O(4*10^9)$，这家的评测机估计是CCF少爷机级别的，所以能过
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=1000010;
ll n,m,k,ans,tot,cnt,prime[N],v[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void pre(ll n){
v[1]=1;
for(ll i=2; i<=n; i++){
if(!v[i]){
prime[++tot]=i;
for(ll j=i*i; j<=n; j+=i) v[j]=1;
}
}
}
inline void solve(ll n){
for(ll i=1; i<=tot&&prime[i]*prime[i]<=n; i++){
ll cnt=1;
while(n%prime[i]==0){
cnt++;
n/=prime[i];
}
ans*=cnt;
}
if(n>1) ans*=2;
}
int main(){
pre(1000000);
for(ll T=read(); T; T--){
n=read(); m=read(); ans=1;
if(m*m>=n){
printf("Case %lld: 0\n",++cnt);
continue;
}
solve(n);
ans/=2;
for(ll i=1; i<m; i++){
if(n%i==0) ans--;
}
printf("Case %lld: %lld\n",++cnt,ans);
}
return 0;
}
```