题目

深度优先搜索算法详解。

输入

2
1 2
1 1000000

输出

1
3626619

思路

算[1,1e6]区间里面每个数的质因子次方数的和。再简化一点，给你一个大数，将它分解它的质因子的乘积的形式。那么就要判素数，两个办法，一个线性筛，一个Miller_rabin，这里数据不大不用Miller_rabin。注意这里数据不大，不用快速乘。

参考文章

Miller-Rabin算法
大数因式分解 Pollard_rho 算法详解
大素数测试的Miller-Rabin算法

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
#define ll long long
#define m_for(i,a,b) for(int i=(a);i<=(b);++i)
int prime[maxn],vis_prime[maxn],cnt_prime;
void Init(){cnt_prime=0;for(int i=2;i<maxn;i++){if(!vis_prime[i])prime[cnt_prime++]=i;for(int j=0;j<cnt_prime&&i*prime[j]<maxn;j++){vis_prime[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
ll sum[maxn];
const int times=10;
ll multi(ll a,ll b,ll m)
{return a*b%m;
//    ll ans=0%m;
//    while(b)
//    {
//        if(b&1)ans=(ans+a)%m,b--;
//        b >>= 1;
//        a=(a+a)%m;
//    }
//    return ans;
}
inline ll m_max(ll a,ll b){return a>b?a:b;}
ll mod,c;
ll f(ll x){return (multi(x,x,mod)+c)%mod;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
inline ll m_abs(ll x){return x>0?x:-x;}
ll find(ll p){if(!(p&1))return 2;if(!vis_prime[p])return p;mod=p;ll a,b;a=b=rand()%(p-2)+2,c=rand()%(p-2)+2;do{a=f(a);b=f(f(b));ll x=gcd(m_abs(a-b),p);if(x>1&&x<p)return x;}while(a!=b);return find(p);
}
int factor_cnt=0;
void Pollard_rho(ll x){if(x<=1)return;if(!vis_prime[x]){factor_cnt++;return ;}ll u=find(x);Pollard_rho(u);Pollard_rho(x/u);
}int main(){Init();for(int i=1;i<maxn;i++){factor_cnt=0;Pollard_rho(i);sum[i]=sum[i-1]+factor_cnt;}int T,a,b;scanf("%d",&T);while(T--){scanf("%d%d",&a,&b);printf("%lld\n",sum[b]-sum[a-1]);}return 0;
}
// from kk