首页 > 代码库 > BZOJ2154: Crash的数字表格

BZOJ2154: Crash的数字表格

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2154

题意&&题解:http://www.cnblogs.com/jianglangcaijin/archive/2013/11/27/3446169.html

我只是来发泄的!!!怎么每次打数论题都会被爆int,爆long long这种问题纠缠好久!!!!!!!!!!

我还以为这题是双倍经验呢

代码:

技术分享
  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 10000000+5 26  27 #define eps 1e-10 28  29 #define ll long long 30  31 #define pa pair<int,int> 32  33 #define for0(i,n) for(int i=0;i<=(n);i++) 34  35 #define for1(i,n) for(int i=1;i<=(n);i++) 36  37 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 38  39 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 40  41 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 42  43 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) 44 #define mod 20101009 45  46 using namespace std; 47  48 inline int read() 49  50 { 51  52     int x=0,f=1;char ch=getchar(); 53  54     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();} 55  56     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();} 57  58     return x*f; 59  60 } 61 int p[maxn],tot,mu[maxn]; 62 bool v[maxn]; 63 void get(int m) 64 { 65     mu[1]=1; 66     for2(i,2,m) 67     { 68         if(!v[i])p[++tot]=i,mu[i]=-1; 69         for1(j,tot) 70         { 71             int k=i*p[j]; 72             if(k>m)break; 73             v[k]=1; 74             if(i%p[j])mu[k]=-mu[i]; 75             else {mu[k]=0;break;} 76         } 77     } 78     for1(i,m)mu[i]=((ll)mu[i]*i%mod*i%mod+mu[i-1])%mod; 79 } 80 inline int sum(int n,int m) 81 { 82     return ((ll)n*(n+1)/2%mod)*((ll)m*(m+1)/2%mod)%mod; 83 } 84 inline int f(int n,int m) 85 { 86     int ret=0; 87     if(n>m)swap(n,m); 88     for(int i=1,j;i<=n;i=j+1) 89     { 90         j=min(n/(n/i),m/(m/i)); 91         ret=(ret+(ll)(mu[j]-mu[i-1])*sum(n/i,m/i)%mod)%mod; 92     } 93     return ret; 94 } 95  96 int main() 97  98 { 99 100     freopen("input.txt","r",stdin);101 102     freopen("output.txt","w",stdout);103         int n=read(),m=read(),ans=0;get(m);104         if(n>m)swap(n,m);105         for(int i=1,j;i<=n;i=j+1)106         {107             j=min(n/(n/i),m/(m/i));108             ans=(ans+(ll)(i+j)*(j-i+1)/2%mod*f(n/i,m/i)%mod)%mod;109         }110         printf("%d\n",(ans+mod)%mod);111 112     return 0;113 114 }  
View Code

 

BZOJ2154: Crash的数字表格