2020牛客NOIP赛前集训营-提高组(第二场)A GCD

it2025-07-16  2

文章目录

R e s u l t Result Result H y p e r l i n k Hyperlink Hyperlink D e s c r i p t i o n Description Description S o l u t i o n Solution Solution C o d e Code Code

R e s u l t Result Result


H y p e r l i n k Hyperlink Hyperlink

https://ac.nowcoder.com/acm/contest/7607/A


D e s c r i p t i o n Description Description

f ( x ) f(x) f(x)表示 x x x除了1以外的所有因数的 g c d gcd gcd,求 ∑ i = a b f ( x ) \sum _{i=a}^b f(x) i=abf(x) 数据范围: 1 < a < b ≤ 1 0 7 1<a<b\leq 10^7 1<a<b107


S o l u t i o n Solution Solution

s i = ∑ j = 1 i f ( i ) s_i=\sum_{j=1}^i f(i) si=j=1if(i),则 A n s = s b − s a − 1 Ans=s_b-s_{a-1} Ans=sbsa1 考虑如何求 f f f,再做前缀和

x x x为质数时, f ( x ) = x f(x)=x f(x)=x x x x的质因子只有一个质数时,则 f ( x ) f(x) f(x)就等于它的最小质因子 否则 f ( x ) = 1 f(x)=1 f(x)=1

用线性筛处理上述过程,时间复杂度 O ( m a x { a , b } ) O(max\{a,b\}) O(max{a,b})


C o d e Code Code

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define MAXN 10000010 using namespace std;LL a,b,s[MAXN]; int prime[MAXN],m,vis[MAXN],tot; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline void prework(LL N) { for(register int i=2;i<=N;i++) { if(vis[i]==0) { s[i]=vis[i]=i;prime[++m]=i; } for(register int j=1;j<=m&&prime[j]*i<=N;j++) { if(prime[j]>vis[i]) break; vis[i*prime[j]]=prime[j]; if(!s[i*prime[j]]) { if(s[i]==1||s[prime[j]]==1) {s[i*prime[j]]=1;continue;}//在此之前已经含有不同的质因子了 if(vis[i]==vis[prime[j]]) s[i*prime[j]]=vis[i];//如果质因子相同,答案就是它的最小质因子 else s[i*prime[j]]=1;//不相同表明有不相同的质因子 } } } for(register int i=1;i<=N;i++) s[i]+=s[i-1];//做前缀和 return; } signed main() { a=read();b=read(); prework(max(a,b)); printf("%lld",s[b]-s[a-1]); }
最新回复(0)