old/under_count.cpp

Back to top page

• category: old
• View this file on GitHub
  • Last commit date: 2019-11-09 02:16:51+09:00

Code

#include <iostream>
using namespace std;

long long power(long long x, long long n)
{
  if (n == 0)
  {
    return 1;
  }
  else if (n % 2 == 1)
  {
    return (x * power(x, n - 1));
  }
  else
  {
    long long half = power(x, n / 2);
    return (half * half);
  }
}

long long under_count(long long N, long long x)
{
  // N未満の自然数に、xが何個あるか。ただしxは 1 から 9 。
  // Nは10^16くらいまで
  long long ans = 0;
  for (auto i = 0; i < 16; i++)
  {
    ans += N / power(10, i + 1) * power(10, i);
    long long y = N % power(10, i + 1);
    if (power(10, i) * x < y && y <= power(10, i) * (x + 1))
    {
      ans += y - power(10, i) * x;
    }
    else if (power(10, i) * (x + 1) < y)
    {
      ans += power(10, i);
    }
  }
  return ans;
}

int main()
{
  long long N;
  cin >> N;
  cout << under_count(N + 1, 1) << endl;
}

#line 1 "old/under_count.cpp"
#include <iostream>
using namespace std;

long long power(long long x, long long n)
{
  if (n == 0)
  {
    return 1;
  }
  else if (n % 2 == 1)
  {
    return (x * power(x, n - 1));
  }
  else
  {
    long long half = power(x, n / 2);
    return (half * half);
  }
}

long long under_count(long long N, long long x)
{
  // N未満の自然数に、xが何個あるか。ただしxは 1 から 9 。
  // Nは10^16くらいまで
  long long ans = 0;
  for (auto i = 0; i < 16; i++)
  {
    ans += N / power(10, i + 1) * power(10, i);
    long long y = N % power(10, i + 1);
    if (power(10, i) * x < y && y <= power(10, i) * (x + 1))
    {
      ans += y - power(10, i) * x;
    }
    else if (power(10, i) * (x + 1) < y)
    {
      ans += power(10, i);
    }
  }
  return ans;
}

int main()
{
  long long N;
  cin >> N;
  cout << under_count(N + 1, 1) << endl;
}

Back to top page