fork download
copy 
  1. /*********************/
  2. //Hard work beats talent when talent doesn’t work hard
  3. // 1% talent but 99% belive and hard work
  4. /*********************/
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. #include<bits/stdc++.h>
  10.  
  11. #define int long long
  12. #define ll long long
  13. #define wh while (t--)
  14. #define  popcount __builtin_popcountll
  15. #define beg begin()
  16. #define pb push_back
  17. #define endi end()
  18. #define f first
  19. #define sec second
  20. #define endl '\n'
  21. #define mem(arr) memset(arr,0,sizeof arr)
  22. #define iso ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  23. //freopen ("text_file.txt", "w", stdout);
  24. ll gcd(ll x, ll y) {
  25.     return (y == 0 ? x : gcd(y, x % y));
  26. }
  27.  
  28. ll lcm(ll x, ll y) {
  29.     return (x / gcd(x, y)) * y;
  30. }
  31. const int MOD =998244353 ;
  32. int n ;
  33. int binary_se(int num)
  34. {
  35.     int l =1 ;
  36.     int r =num ;
  37.     int maxi =1e9 ;
  38.     while(l<=r)
  39.     {
  40.         int mid =(l+r)>>1ll ;
  41.         //cout<<mid<<endl ;
  42.         if((num*num-mid*mid)<=n&&num!=mid)
  43.         {
  44.            //cout<<mid<<" "<<num<<" "<<n<<endl ;
  45.             maxi =min(maxi,mid) ;
  46.             r=mid-1 ;
  47.         }
  48.         else
  49.             l =mid+1 ;
  50.     }
  51.     if(maxi==1e9)
  52.     {
  53.         return -1 ;
  54.     }
  55.     return maxi ;
  56. }
  57. int32_t main() {
  58.     //freopen("text_file.txt", "w", stdout);
  59.     iso;
  60.  cin>> n ;
  61.  int ans =0 ;
  62.  for(int i=1 ;i*i<=1e12;i++)
  63.  {
  64.      int x =binary_se(i) ;
  65.    //
  66.    if(x==-1)
  67.    {
  68.        continue;
  69.    }
  70.    cout<<i<<" "<<x<<endl ;
  71.      ans=(ans%MOD+(i-x)%MOD)%MOD ;
  72.  }
  73.  for(int i=1 ;i*i<=n ;i++)
  74.  {
  75.      ans++ ;
  76.      ans%=MOD ;
  77.  }
  78.  cout<<ans<<endl ;
  79. }
Success #stdin #stdout 0.03s 5676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5VgRxT
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!