30分为什么这么多RE
  • 板块P3601 签到题
  • 楼主Jason101
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/20 11:16
  • 上次更新2025/1/20 13:46:37
查看原帖
30分为什么这么多RE
1028310
Jason101楼主2025/1/20 11:16
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
long long l,r,a[N];
int p[N], cnt;
bool flag[N];
void phi(){
    for(int i=2; i<=N; i++){
        if(!flag[i]) p[++cnt] = i;
        for(int j=1; j<=cnt; j++){
            if(i * p[j] > N)
			break;
            flag[i * p[j]] = 1;
            if(i % p[j] == 0) 
			break;
        }
    }
}
int main(){
    phi();
    cin >> l >> r;
    for(long long i=l; i<=r; i++)
        a[i - l + 1] = i; 

    for(int i=1; i<=cnt; i++){
        long long j = l / p[i];
        while(p[i] * j <= r){
            if(p[i] * j >= l)
            a[p[i]*j-l+1]=a[p[i]*j-l+1]/p[i]*(p[i]-1);
            j++; 
        }
    }
    long long ans=0;
    for(long long i=l; i<=r; i++){
        ans+=i-a[i-l+1];
        ans%=666623333;
    }
    cout<<ans<<"\n";
}
2025/1/20 11:16
加载中...