CSL 爱勾股

C++11(clang++ 3.9) 解法, 执行用时: 306ms, 内存消耗: 5192K, 提交时间: 2019-03-31 17:51:09
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define forsaken
#ifdef forsaken
  #define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
#else
  #define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(a,b) memset(a,b,sizeof(a))
#define msn(a,n,b) for(int i=0;i<=n;i++)a[i]=b
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define fi first
#define se second
using namespace std;
mt19937 rng_32(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const int mod=998244353,inv_2=(mod+1)>>1,inv6=166374059;
const int seed=233;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int max_n=100005;
namespace {
    inline int Add(int x,int y){return (x+=y)>=mod?x-mod:x;}
	inline int Sub(int x,int y){return (x-=y)<0?x+mod:x;}
    inline int Mul(int x,int y) {return 1ll*x*y%mod;}
    inline int Pow(int x,int y=mod-2){int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
}
ll f(ll a,ll b,ll c,ll n)
{
    ll m = (a*n+b)/c;
    if(n==0||m==0) return (b/c)%mod;
    if(n==1) return ((b/c)+((a+b)/c))%mod;
    if(a<c&&b<c) return ((1ll*m%mod*n%mod - f(c,c-b-1,a,m-1))%mod+mod)%mod;
    else return (((1ll*(a/c)%mod*n%mod*(n+1)%mod*inv_2%mod )%mod + (b/c)%mod*(n+1)%mod) + f(a%c,b%c,c,n)%mod);
}
int n,q;
int Sqr;
int m;
ll w[max_n*2],g[max_n*2][4];
int ID(int x){return x<=Sqr?m+1-x:n/x;}
int cnt;
bool p[max_n];
int pri[max_n];
int pre[max_n][4];
void sieve(int n)
{
    p[0]=p[1]=true;
    for(int i=2;i<=n;i++)
    {
        if(!p[i])
        {
            pri[++cnt]=i;
            for(int r=0;r<4;r++)pre[cnt][r]=pre[cnt-1][r]+(i%4==r);
        }
        for(int j=1;j<=cnt&&1ll*pri[j]*i<=n;j++)
        {
            p[i*pri[j]]=true;
            if(i%pri[j]==0)break;
        }
    }
}
int cal(int n,int r)
{
    if(r==0)return n/4;
    return n/4+(n%4>=r)-(r==1);
}
int f(int p,int k)
{
    if(p%4==1)return 2*k+1;
    return 1;
}
ll s[max_n];
ll sum[max_n];
int x;
void init(int n)
{
    Sqr=sqrt(n);m=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        w[++m]=n/l;
        for(int r=0;r<4;r++)g[m][r]=cal(w[m],r);
        r=n/(n/l);
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=m&&1ll*pri[i]*pri[i]<=w[j];j++)
        {
            int k=ID(w[j]/pri[i]);
            for(int r=0;r<4;r++)
            {
                int rr=r*pri[i]%4;
                g[j][rr]-=g[k][r]-pre[i-1][r];
            }
        }
    }
    for(int i=cnt;i>=1;i--)
    {
        for(int j=1;j<=m&&1ll*pri[i]*pri[i]<=w[j];j++)
        {
            ll t1=pri[i],t2=1ll*pri[i]*pri[i];
            for(int e=1;t2<=w[j];e++,t1=t2,t2*=pri[i])
            {
                int k=ID(w[j]/t1);
                s[j]+=f(pri[i],e)*(s[k]+3*(g[k][1]-pre[i][1])+g[k][2]-pre[i][2]+g[k][3]-pre[i][3])+f(pri[i],e+1);
            }
        }
    }
    for(int j=1;j<=m;j++)s[j]+=g[j][1]*3+g[j][2]+g[j][3];
    for(int j=1;j<=m;j++)s[j]=(s[j]+1-w[j])/2;
    for(int j=1;j<=m;j++)s[j]=f(4,3,5,s[j])%mod;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        int k=ID(n/l);
        sum[k]=Add(sum[k-1],Mul(r-l+1,s[k]));
    }
}
int solve(int x)
{
    if(x==0)return 0;
    int nn=n/x;
    int k=ID(nn);
    int res=sum[k];
    res=Sub(res,Mul(n/nn-x,s[k]));
    return res;
}
int main()
{
    scanf("%d%d",&n,&q);
    sieve(max_n-1);
    init(n);
    for(int i=0;i<q;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",Sub(solve(r),solve(l-1)));
    }
}
详情
