题目描述

样例

input: 5 7 output: 13

分析

分析式子$f(x)=gcd(所有因子)$ 如果$x$不是由一个数的次幂得到的，那么$x$肯定有2个以上的质因子，所以这些因子的$gcd$就是1。 而对于$x=p^i$，则$gcd$为$p$。

由此，可以得到一个大胆的想法，先将ans定为$b-a+1$。枚举数的次幂，如果是在$a,b$之间的，那么就把答案更新，即原来是1，那么要把1改成p，最后对$ans$的影响就是$ans=ans-1+p$。

注意：1、要开long long!!!    \qquad\,\, 2、只要枚举素数的次幂，因此要素数筛。

代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int MAXN=1e7+10; ll pr[MAXN]; int p[MAXN],cnt=0; int main() { ll a,b; memset(p,0,sizeof(p)); for(ll i=2;i<=1e7;i++){ if(!p[i]){ for(ll j=i*2;j<=1e7;j+=i) p[j]=1; pr[++cnt]=i; } }//筛 scanf("%lld%lld",&a,&b); ll ans=b-a+1ll; for(ll i=1;i<=cnt;i++){ for(ll j=pr[i];j<=b;j*=pr[i]){//枚举b以内的次幂 if(j>=a) ans=ans-1ll+pr[i];//若在区间内，则更新答案 } } printf("%lld\n",ans); } //4729362 9152241 //1946482123177 //大样例

END

要开long long!!!