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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2440: [中山市选2011]完全平方数(二分+莫比乌斯函数)  

2014-07-08 13:22:00|  分类: oi,bzoj,数论,二 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先直接求不好求,考虑二分,那么就是求[1..mid]里符合条件的数有几个,首先可以很简单的想到容斥,不过略麻烦,所以可以直接用莫比乌斯函数求掉。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • typedef long long ll ;

  •  

  • const ll maxn = 100000 ;

  •  

  • bool f[ maxn + 10 ] ;

  • ll u[ maxn + 10 ] ;

  •  

  • inline void Init(  ) {

  •         memset( f , true , sizeof( f ) ) ;

  •         f[ 1 ] = false , u[ 1 ] = 1 ;

  •         for ( ll i = 2 ; i <= maxn ; ++ i ) if ( f[ i ] ) {

  •                 u[ i ] = -1 ;

  •                 for ( ll j = i << 1 ; j <= maxn ; j += i ) {

  •                         f[ j ] = false ;

  •                         if ( ( j / i ) % i ) u[ j ] = - u[ j / i ] ; else u[ j ] = 0 ;

  •                 }

  •         }

  • }

  •  

  • inline ll cal( ll n ) {

  •         ll ret = ll( sqrt( n ) ) ;

  •         ll rec = 0 ;

  •         for ( ll i = 1 ; i <= ret ; ++ i ) rec += ll( u[ i ] * n / ( i * i ) ) ;

  •         return rec ;

  • }

  •  

  • inline ll solve( ll k ) {

  •         ll l = 0 , r = k << 2 , mid ;

  •         while ( r - l > 1 ) {

  •                 mid = ( l + r ) >> 1 ;

  •                 if ( cal( mid ) < ll( k ) ) l = mid ; else r = mid ;

  •         }

  •         return r ;

  • }

  •  

  • int main(  ) {

  •         Init(  ) ;

  •         ll T ; scanf( "%lld" , &T ) ;

  •         while ( T -- ) {

  •                 ll k ; scanf( "%lld" , &k ) ;

  •                 printf( "%lld\n" , solve( k ) ) ;

  •         }

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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