bzoj 4407 于神之怒加强版（反演+线性筛）-白红宇

bzoj 4407 于神之怒加强版（反演+线性筛）

阅读量：5225 次

发布时间：2019-06-14

本文共 1329 字，大约阅读时间需要 4 分钟。

于神之怒加强版

Time Limit: 80 Sec Memory Limit: 512 MB

Submit: 1184 Solved: 535

[][][]

Description

给下N,M,K.求

Input

输入有多组数据，输入数据的第一行两个正整数T,K，代表有T组数据，K的意义如上所示，下面第二行到第T+1行，每行为两个正整数N,M，其意义如上式所示。

Output

如题

Sample Input

1 2

3 3

Sample Output

HINT

1<=N,M,K<=5000000,1<=T<=2000

题解：

Source

1 #include
      
        2 #pragma GCC optimize(2) 3 #pragma G++ optimize(2) 4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 10 #define ll long long11 #define inf 100000000012 #define mod 100000000713 #define N 500000714 using namespace std;15 inline int read()16 {17 int x=0,f=1;char ch=getchar();18 while(!isdigit(ch)){ if(ch=='-')f=-1;ch=getchar();}19 while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}20 return x*f;21 }22 23 int F[N],f[N],flag[N],k,tot,p[N],ans;24 inline int gpow(int x,int y)25 {26 int ans=1;27 while (y)28 {29 if (y&1) ans=(ll)ans*x%mod;30 y>>=1;x=(ll)x*x%mod;31 }32 return ans;33 }34 void preparation()35 {36 F[1]=1;37 for (int i=2;i
            
             m) swap(n,m);ans=0;56 for (int i=1,pos=0;i<=n;i=pos+1)57 {58 pos=min(n/(n/i),m/(m/i));59 (ans+=1LL*(n/i)*(m/i)%mod*(F[pos]-F[i-1])%mod)%=mod;60 }61 printf("%d\n",(ans+mod)%mod);62 }63 return 0;64 }