注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2154: Crash的数字表格 && BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块)  

2014-07-19 20:14:00|  分类: 莫比乌斯函数,数 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:

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

http://www.lydsy.com/JudgeOnline/problem.php?id=2693


(发题解攒RP啦~~~本来这两题一直拖着没写的,然后LJT大神问了之后没事就去想了一下,顺便A掉除除草嗯,这次要写一篇详细题解!(谁叫我是数论渣渣。。。))

大意是给定n,m求sigma(lcm(i,j))1<=i<=n,1<=j<=m,2154只处理一个查询,2693要求多个查询 N,M<=1000W


首先还是暴力的来推一推公式嗯,还是公式最明了了嗯:

BZOJ-2154: Crash的数字表格  BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块) - cjjlsdy - cjjlsdy的博客

考虑求解:

BZOJ-2154: Crash的数字表格  BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块) - cjjlsdy - cjjlsdy的博客

BZOJ-2154: Crash的数字表格  BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块) - cjjlsdy - cjjlsdy的博客

那么

BZOJ-2154: Crash的数字表格  BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块) - cjjlsdy - cjjlsdy的博客

再来考虑求最终答案:

BZOJ-2154: Crash的数字表格  BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块) - cjjlsdy - cjjlsdy的博客

事实上到了这一步之后就可以求解2154了,在求F(n,m)中分块,在求Ans(n,m)中也分块处理,这样的时间复杂度是O(sqrt(n)*sqrt(n))=O(n),用线性筛法求u(d)d^2(u(d)表示莫比乌斯函数),总复杂度仍然是O(n),但是这样没法做到快速支持多组查询,所以还要继续化简:

BZOJ-2154: Crash的数字表格  BZOJ-2693: jzptab 详细题解 (莫比乌斯函数+分块) - cjjlsdy - cjjlsdy的博客

然后我们惊奇的发现H(D)是可以用线性筛顺便求出,那么对D分块,处理出一个H(D)的前缀和,这样就可以在O(sqrt(n))的时间内处理出一个询问了,所以总复杂度是O(n)-O(sqrt(n)),这样就可以解决2693啦。


代码:

2693:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • typedef long long ll ;

  •  

  • const ll maxn = 10100000 ;

  • const ll maxt = 10100 ;

  • const ll mod = 100000009 ;

  •  

  • bool flag[ maxn ] ;

  • ll p[ maxn ] , pn = 0 , query[ maxt ][ 2 ] , t , mn = 0 ;

  • ll H[ maxn ] , pre[ maxn ] ;

  •  

  • inline void Init(  ) {

  •         for ( ll i = 0 ; i ++ < mn ; ) flag[ i ] = true ;

  •         H[ 1 ] = 1 ;

  •         for ( ll i = 2 ; i <= mn ; ++ i ) {

  •                 if ( flag[ i ] ) {

  •                         p[ ++ pn ] = i , H[ i ] = ( - ( ( i * i ) % mod ) + i + mod ) % mod ;

  •                 }

  •                 for ( ll j = 1 ; j <= pn && i * p[ j ] <= mn ; ++ j ) {

  •                         flag[ i * p[ j ] ] = false ;

  •                         if ( i % p[ j ] ) H[ i * p[ j ] ] = H[ i ] * H[ p[ j ] ] % mod ; else {

  •                                 H[ i * p[ j ] ] = ll( p[ j ] ) * H[ i ] % mod ; break ;

  •                         }

  •                 }

  •         }

  •         pre[ 0 ] = 0 ;

  •         for ( ll i = 0 ; i ++ < mn ; ) pre[ i ] = ( pre[ i - 1 ] + H[ i ] ) % mod ;

  • }

  •  

  • inline ll sum( ll n , ll m ) {

  •         return ( ( n * ( n + 1 ) / ll( 2 ) ) % mod ) * ( ( m * ( m + 1 ) / ll( 2 ) ) % mod ) % mod ;

  • }

  •  

  • #define sumh( l , r ) ( ( pre[ r ] - pre[ l - 1 ] + mod ) % mod )

  •  

  • inline ll solve( ll n , ll m ) {

  •         ll ans = 0 ;

  •         if ( n > m ) swap( n , m ) ;

  •         for ( ll i = 1 , j , v ; i <= n ; ) {

  •                 j = min( n / ( n / i ) , m / ( m / i ) ) ;

  •                 v = ( sumh( i , j ) * sum( n / i , m / i ) ) % mod ;

  •                 ( ans += v ) %= mod ;

  •                 i = j + 1 ;

  •         }

  •         return ll( ans ) ;

  • }

  •  

  • int main(  ) {

  •         scanf( "%lld" , &t ) ;

  •         for ( ll i = 0 ; i ++ < t ; ) {

  •                 scanf( "%lld%lld"  , query[ i ] , query[ i ] + 1 ) ;

  •                 mn = max( mn , max( query[ i ][ 0 ] , query[ i ][ 1 ] ) ) ;

  •         }

  •         Init(  ) ;

  •         for ( ll i = 0 ; i ++ < t ; ) printf( "%lld\n" , solve( ll( query[ i ][ 0 ] ) , ll( query[ i ][ 1 ] ) ) ) ;

  •         return 0 ;

  • }


2154:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • typedef long long ll ;

  •  

  • const ll maxn = 10100000 ;

  • const ll maxt = 10100 ;

  • const ll mod = 20101009 ;

  •  

  • bool flag[ maxn ] ;

  • ll p[ maxn ] , pn = 0 , query[ maxt ][ 2 ] , t , mn = 0 ;

  • ll H[ maxn ] , pre[ maxn ] ;

  •  

  • inline void Init(  ) {

  •         for ( ll i = 0 ; i ++ < mn ; ) flag[ i ] = true ;

  •         H[ 1 ] = 1 ;

  •         for ( ll i = 2 ; i <= mn ; ++ i ) {

  •                 if ( flag[ i ] ) {

  •                         p[ ++ pn ] = i , H[ i ] = ( - ( ( i * i ) % mod ) + i + mod ) % mod ;

  •                 }

  •                 for ( ll j = 1 ; j <= pn && i * p[ j ] <= mn ; ++ j ) {

  •                         flag[ i * p[ j ] ] = false ;

  •                         if ( i % p[ j ] ) H[ i * p[ j ] ] = H[ i ] * H[ p[ j ] ] % mod ; else {

  •                                 H[ i * p[ j ] ] = ll( p[ j ] ) * H[ i ] % mod ; break ;

  •                         }

  •                 }

  •         }

  •         pre[ 0 ] = 0 ;

  •         for ( ll i = 0 ; i ++ < mn ; ) pre[ i ] = ( pre[ i - 1 ] + H[ i ] ) % mod ;

  • }

  •  

  • inline ll sum( ll n , ll m ) {

  •         return ( ( n * ( n + 1 ) / ll( 2 ) ) % mod ) * ( ( m * ( m + 1 ) / ll( 2 ) ) % mod ) % mod ;

  • }

  •  

  • #define sumh( l , r ) ( ( pre[ r ] - pre[ l - 1 ] + mod ) % mod )

  •  

  • inline ll solve( ll n , ll m ) {

  •         ll ans = 0 ;

  •         if ( n > m ) swap( n , m ) ;

  •         for ( ll i = 1 , j , v ; i <= n ; ) {

  •                 j = min( n / ( n / i ) , m / ( m / i ) ) ;

  •                 v = ( sumh( i , j ) * sum( n / i , m / i ) ) % mod ;

  •                 ( ans += v ) %= mod ;

  •                 i = j + 1 ;

  •         }

  •         return ll( ans ) ;

  • }

  •  

  • int main(  ) {

  •         t = 1 ;

  •         for ( ll i = 0 ; i ++ < t ; ) {

  •                 scanf( "%lld%lld"  , query[ i ] , query[ i ] + 1 ) ;

  •                 mn = max( mn , max( query[ i ][ 0 ] , query[ i ][ 1 ] ) ) ;

  •         }

  •         Init(  ) ;

  •         for ( ll i = 0 ; i ++ < t ; ) printf( "%lld\n" , solve( ll( query[ i ][ 0 ] ) , ll( query[ i ][ 1 ] ) ) ) ;

  •         return 0 ;

  • }


  评论这张
 
阅读(649)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017