2020智算之道复赛 D - 分数（素筛）
这题我背最大的锅，这种题目显然是考虑所有分母的
L
C
M
LCM
LCM，今年的校赛我还出过一道这样的题，然而比赛时我竟然是找规律凭第一感觉判断的，真的tcl
对于第 i i i个数，我们需要的只是考虑他的前缀所有分母的 L C M ( 1 , 2 , 3 , . . . , i − 1 ) LCM(1,2,3,...,i-1) LCM(1,2,3,...,i−1)，而 L C M LCM LCM的本质就是取同类质因子的 m a x max max，打表或者手写前几十个数，不难发现这样的规律：只有含单个质因子的数才会贡献一次答案，而贡献的就是它的唯一质因子。那么对于这样的数我们只需素筛，然后找每种质因子在最大范围所有的次幂数并打上标记，然后从前向后更新答案
赛后补题多写了一个 O ( n ) O(n) O(n)循环就 T L E TLE TLE了，多开一个数组就 M L E MLE MLE了，实际上我们只需要在欧拉筛的过程中计算答案
更让我没想到的是，比赛时一开始是直接对 1 L L < < 32 1LL<<32 1LL<<32取模，然后发现根据位运算的性质可以优化为 x & ( ( 1 L L < < 32 ) − 1 ) x\&((1LL<<32)-1) x&((1LL<<32)−1)，实际上 2 32 2^{32} 232不就是 u n s i g n e d i n t unsigned~~int unsigned int的最大范围吗，根据无符号整型数自然溢出的性质，直接计算即可，妙啊
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const ll Mod=(1LL<<32)-1;
const int maxn=8e7+10;
const int maxm=5e6+10;
int cnt,n;
int f[maxn],prime[maxm];
bool isprime[maxn];
unsigned int a,b;
void eular(int n){
for(int i=2;i<=n;i++){
if(!isprime[i]){
prime[cnt++]=i;
ll x=i;
while(x<=n){
f[x]=i;
x=x*i;
}
}
if(f[i]) a=a*f[i]+b;
for(int j=0;j<cnt && i*prime[j]<=n;j++){
isprime[i*prime[j]]=1;
if (i%prime[j]==0) break;
}
}
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
scanf("%d%u%u",&n,&a,&b);
eular(n);
printf("%u\n",a);
return 0;
}