筛[l,r]之间的合数
l<=r<=1e12
r-l<=1e6
筛小于等于r的合数所需的质因子大小最多不会超过根号r(<=1e6)
模板:
const int N=1e6+5;
bool not_prime_small[N]={false};
bool not_prime_big[N]={false};
void segment_seive(ll a,ll b)
{
mem(not_prime_big,false);
if(a==1)not_prime_big[0]=true;
for(ll i=2;i*i<=b;i++)
{
if(!not_prime_small[i])
{
for(ll j=i+i;j*j<=b;j+=i)
{
not_prime_small[j]=true;
}
for(ll j=max(2ll,(a+i-1)/i)*i;j<=b;j+=i)
not_prime_big[j-a]=true;
}
}
}
例题1:POJ 2689 Prime Distance
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define pb push_back
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1e6+5;
bool not_prime_small[N]={false};
bool not_prime_big[N]={false};
vector<ll>s;
void segment_seive(ll a,ll b)
{
s.clear();
mem(not_prime_big,false);
if(a==1)not_prime_big[0]=true;
for(ll i=2;i*i<=b;i++)
{
if(!not_prime_small[i])
{
for(ll j=i+i;j*j<=b;j+=i)
{
not_prime_small[j]=true;
}
for(ll j=max(2ll,(a+i-1)/i)*i;j<=b;j+=i)
not_prime_big[j-a]=true;
}
}
for(ll i=a;i<=b;i++)
if(!not_prime_big[i-a])s.pb(i);
if(s.size()<=1)cout<<"There are no adjacent primes."<<endl;
else
{
pair<ll,ll>ans,_ans;
int mx=0,mn=0x3f3f3f3f;
for(int i=0;i<s.size()-1;i++)
{
//cout<<s[i]<<endl;
if(s[i+1]-s[i]>mx)
{
mx=s[i+1]-s[i];
ans.first=s[i];
ans.second=s[i+1];
}
if(s[i+1]-s[i]<mn)
{
mn=s[i+1]-s[i];
_ans.first=s[i];
_ans.second=s[i+1];
}
}
cout<<_ans.first<<","<<_ans.second<<" are closest, "<<ans.first<<","<<ans.second<<" are most distant."<<endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll l,u;
while(cin>>l>>u)
{
segment_seive(l,u);
}
return 0;
}
View Code
例题2:HDU 6069 Counting Divisors
要运用到约数个数定理
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1e6+5;
const int MOD=998244353;
bool not_prime[N]={false};
ll ans[N];
ll val[N];
vector<int>prime;
void prime_seive()
{
for(int i=2;i<N;i++)
{
if(!not_prime[i])
{
prime.pb(i);
}
for(int j=0;i*prime[j]<N;j++)
{
not_prime[i*prime[j]]=true;
if(i%prime[j]==0)break;
}
}
}
void solve(ll l,ll r,ll k)
{
for(ll i=l;i<=r;i++)
{
ans[i-l]=1;
val[i-l]=i;
}
for(int i=0;i<prime.size();i++)
{
for(ll j=max(2ll,(l+prime[i]-1)/prime[i])*prime[i];j<=r;j+=prime[i])
{
int tot=0;
if(val[j-l]%prime[i])continue;
while(val[j-l]%prime[i]==0)tot++,val[j-l]/=prime[i];
ans[j-l]=(1+tot*k)%MOD*ans[j-l]%MOD;
}
}
for(int i=0;i<=r-l;i++)
{
if(val[i]>1)ans[i]=(1+k)%MOD*ans[i]%MOD;
}
ll _ans=0;
for(int i=0;i<=r-l;i++)
_ans=(_ans+ans[i])%MOD;
cout<<_ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll l,r,k;
int T;
prime_seive();
cin>>T;
while(T--)
{
cin>>l>>r>>k;
solve(l,r,k);
}
return 0;
}
View Code
转载于:https://www.cnblogs.com/widsom/p/7766243.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)