Friday 28 July 2017

Lightoj 1289 - LCM from 1 to n

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<string>
  8. #include<map>
  9. #include<set>
  10. #include<vector>
  11. #include<queue>
  12. #include<bitset>
  13.  
  14. using namespace std;
  15.  
  16. #define clr( x , y ) memset(x,y,sizeof(x))
  17. #define cls( x ) memset(x,0,sizeof(x))
  18. #define mp make_pair
  19. #define pb push_back
  20. typedef long long lint;
  21. typedef long long ll;
  22. typedef long long LL;
  23. const int maxn = 1e8 + 5 ;
  24. const int pnum = 5761460 ;
  25. bitset<maxn>noprime ;
  26. unsigned int mul[pnum] ;
  27. int p[pnum] , len ;
  28. int sieve(){
  29.     noprime.reset() ;
  30.     for( int i = 2 ; i * i <= maxn ; i++ ){
  31.         if( !noprime[i] ){
  32.             for( int j = i * i ; j <= maxn ; j += i ){
  33.                 noprime[j] = 1 ;
  34.             }
  35.         }
  36.     }
  37.     int k = 0 ;
  38.     for( int i = 2 ; i <= maxn ; i++ )
  39.         if( !noprime[i] ) p[k++] = i ;
  40.     return k ;
  41. }
  42.  
  43. void init_lcm(){
  44.     len = sieve() ;
  45.     mul[0] = p[0] ;
  46.     for( int i = 1 ; i < len ; i++ )
  47.         mul[i] = mul[i-1] * p[i] ;
  48. }
  49.  
  50. void solve( int n ){
  51.     int pos = lower_bound( p , p + len , n ) - p ;
  52.     if( p[pos] != n ) pos-- ;
  53.     unsigned int ans = mul[pos] ;
  54.     for( int i = 0 ; p[i] * p[i] <= n ; i++ )
  55.     {
  56.         int tmp = p[i] ;
  57.         int tmp2 = p[i] * p[i] ;
  58.         while( tmp2 / tmp == p[i] && tmp2 <= n )
  59.         {
  60.             tmp = tmp * p[i] ;
  61.             tmp2 = tmp2 * p[i] ;
  62.         }
  63.         ans = ans * ( tmp / p[i] ) ;
  64.     }
  65.     cout << ans << endl ;
  66. }
  67. int main(){
  68. // freopen("input.txt","r",stdin);
  69.     int t ; cin >> t ; int kase = 1 ;
  70.     init_lcm() ;
  71.     while( t-- ){
  72.         int n ;
  73.         cin >> n ;
  74.         printf( "Case %d: " , kase++ ) ;
  75.         solve( n ) ;
  76.     }
  77.     return 0;
  78. }

1 comment:

  1. Hello vaia Adab. Can you please tell me, what are the logic behind the (tmp2/tmp == p[i]) on line 58. Thanks in advance.

    ReplyDelete

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...