#748101 (C++17) No.1164 GCD Products hard

提出ソース

結果

問題	No.1164 GCD Products hard
ユーザー	89
提出日時	2022-03-25 00:47:22
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	8,533 bytes
コンパイル時間	815 ms
コンパイル使用メモリ	84,928 KB
実行使用メモリ	70,472 KB
最終ジャッジ日時	2024-10-13 08:15:34
合計ジャッジ時間	8,210 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	--	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <stdio.h>
//#include <atcoder/all>
//#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <vector>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#define ll long long
#define ld long double
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define rep1(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = n; i--;)
#define rrep2(i, n) for (ll i = n; i--;)
#define rrep3(i, a, b) for (ll i = b; i-- > (a);)
#define rrep4(i, a, b, c) for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define each1(i, a) for (auto &&i : a)
#define each2(x, y, a) for (auto &&[x, y] : a)
#define each3(x, y, z, a) for (auto &&[x, y, z] : a)
#define each(...) overload4(__VA_ARGS__, each3, each2, each1)(__VA_ARGS__)
#define elif else if
// // void print()
// // {
// //   putchar(' ');
// // }
// // void print(bool a) { printf("%d", a); }
// // void print(int a) { printf("%d", a); }
// // void print(unsigned a) { printf("%u", a); }
// // void print(long a) { printf("%ld", a); }
// // void print(long long a) { printf("%lld", a); }
// // void print(unsigned long long a) { printf("%llu", a); }
// // void print(char a) { printf("%c", a); }
// // void print(char a[]) { printf("%s", a); }
// // void print(const char a[]) { printf("%s", a); }
// // void print(float a) { printf("%.15f", a); }
// // void print(double a) { printf("%.15f", a); }
// // void print(long double a) { printf("%.15Lf", a); }
// // void print(const string &a)
// // {
// //   for (auto &&i : a)
// //     print(i);
// // }
// // template <class T>
// // void print(const complex<T> &a)
// // {
// //   if (a.real() >= 0)
// //     print('+');
// //   print(a.real());
// //   if (a.imag() >= 0)
// //     print('+');
// //   print(a.imag());
// //   print('i');
// // }
// // template <class T>
// // void print(const vector<T> &);
// // template <class T, size_t size>
// // void print(const array<T, size> &);
// // template <class T, class L>
// // void print(const pair<T, L> &p);
// // template <class T, size_t size>
// // void print(const T (&)[size]);
// // template <class T>
// // void print(const vector<T> &a)
// // {
// //   if (a.empty())
// //     return;
// //   print(a[0]);
// //   for (auto i = a.begin(); ++i != a.end();)
// //   {
// //     putchar(' ');
// //     print(*i);
// //   }
// // }
// // template <class T>
// // void print(const deque<T> &a)
// // {
// //   if (a.empty())
// //     return;
// //   print(a[0]);
// //   for (auto i = a.begin(); ++i != a.end();)
// //   {
// //     putchar(' ');
// //     print(*i);
// //   }
// // }
// // template <class T, size_t size>
// // void print(const array<T, size> &a)
// // {
// //   print(a[0]);
// //   for (auto i = a.begin(); ++i != a.end();)
// //   {
// //     putchar(' ');
// //     print(*i);
// //   }
// // }
// // template <class T, class L>
// // void print(const pair<T, L> &p)
// // {
// //   print(p.first);
// //   putchar(' ');
// //   print(p.second);
// // }
// // template <class T, size_t size>
// // void print(const T (&a)[size])
// // {
// //   print(a[0]);
// //   for (auto i = a; ++i != end(a);)
// //   {
// //     putchar(' ');
// //     print(*i);
// //   }
// // }
// // template <class T>
// // void print(const T &a) { cout << a; }
// // int out()
// // {
// //   putchar('\n');
// //   return 0;
// // }
// // template <class T>
// // int out(const T &t)
// // {
// //   print(t);
// //   putchar('\n');
// //   return 0;
// // }
// // template <class Head, class... Tail>
// // int out(const Head &head, const Tail &...tail)
// // {
// //   print(head);
// //   putchar(' ');
// //   out(tail...);
// //   return 0;
// // }

// // string alphabet = "abcdefghijklmnopqrstuvwxyz";
// // void print_array(vector<ll> a)
// // {
// //   auto L = a.size();
// //   for (int i = 0; i < L; i++)
// //   {
// //     printf("%lld", a[i]);
// //     if (i != L - 1)
// //     {
// //       printf(" ");
// //     }
// //     else
// //     {
// //       printf("\n");
// //     }
// //   }
// // }
// // ll gcd(ll a, ll b)
// // {
// //   if (a % b)
// //     return gcd(b, a % b);
// //   else
// //     return b;
// // }
// void dijkstra(ll s)
// {
//   pq<P, vector<P>, greater<P>> que;
//   fill(d, d + V, 10000000000);
//   d[s] = 0;
//   que.push(P(0, s));
//   while (!que.empty())
//   {
//     P p = que.top();
//     que.pop();
//     ll v = p.second;
//     if (d[v] < p.first)
//       continue;
//     rep(g[v].size())
//     {
//       edge e = g[v][i];
//       if (d[e.to] > d[v] + e.cost)
//       {
//         d[e.to] = d[v] + e.cost;
//         que.push(P(d[e.to], e.to));
//       }
//     }
//   }
// }
/**
 * @brief Union-Find
 * @docs docs/union-find.md
 */
struct UnionFind
{
  vector<int> data;

  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if (x == y)
      return false;
    if (data[x] > data[y])
      swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k)
  {
    if (data[k] < 0)
      return (k);
    return data[k] = find(data[k]);
  }

  int size(int k)
  {
    return -data[find(k)];
  }

  bool same(int x, int y)
  {
    return find(x) == find(y);
  }

  // vector<vector<int> > groups()
  // {
  //   int n = (int)data.size();
  //   vector<vector<int> > ret(n);
  //   for (int i = 0; i < n; i++)
  //   {
  //     ret[find(i)].push_back(i);
  //   }
  //   ret.erase(remove_if(begin(ret), end(ret), [&](const vector<int> &v)
  //                       { return v.empty(); }));
  //   return ret;
  // }
};
// #define pq priority_queue
// struct edge
// {
//   ll to, cost;
// };
// typedef pair<ll, ll> P;
// vector<edge> g[300000];
// ll dist[300000];
// ll dist2[300000];
// ll n, r;
// void dijkstra(ll s)
// {
//   priority_queue<P, vector<P>, greater<P>> que;
//   fill(dist, dist + n, 10000000000);
//   fill(dist2, dist2 + n, 10000000000);
//   dist[s] = 0;
//   que.push(P(0, s));
//   while (!que.empty())
//   {
//     P p = que.top();
//     que.pop();
//     ll v = p.second;
//     ll d = p.first;
//     if (dist2[v] < d)
//       continue;
//     rep(g[v].size())
//     {
//       edge &e = g[v][i];
//       ll d2 = d + e.cost;
//       if (dist[e.to] > d2)
//       {
//         swap(dist[e.to], d2);
//         que.push(P(dist[e.to], e.to));
//       }
//       if (dist2[e.to] > d2 && dist[e.to] < d2)
//       {
//         dist2[e.to] = d2;
//         que.push(P(dist2[e.to], e.to));
//       }
//     }
//   }
//   printf("%ld\n", dist[n - 1]);
//}
// sort(a.begin(), a.end(), [](const vector<ll> &alpha, const vector<ll> &beta)
//      { return alpha[2] > beta[2]; });
ll kruskal(ll n, vector<vector<ll>> edge)
{
  ll res = 0;
  UnionFind a(n);
  for (int i = 0; i < edge.size(); i++)
  {
    if (!a.same(edge[i][0], edge[i][1]))
    {
      res += edge[i][2];
      a.unite(edge[i][0], edge[i][1]);
    }
  }
  return res;
}
// sort(a.begin(), a.end(), [](const vector<ll> &alpha, const vector<ll> &beta)
//      { return alpha[2] < beta[2]; });
long long modpow(long long a, long long n, long long mod)
{
  long long res = 1;
  while (n > 0)
  {
    if (n & 1)
      res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
ll MOD = 1000000007;
int main()
{
  ll a, b, n;
  cin >> a >> b >> n;
  ll res = 1;
  ll cnt[b + 2];
  rep(i, b + 2)
  {
    // cout << i << endl;
    cnt[i] = 0;
  }
  for (int i = b; i > 1; i--)
  {
    // cout << i << endl;
    ll t = b / i - (a - 1) / i;
    // cout << t << endl;
    cnt[i] = modpow(t, n, MOD);
    rep(j, 2, 1000000000)
    {
      if (j * i > b)
        break;
      cnt[i] -= cnt[i * j];
      cnt[i] %= MOD;
    }
    //cout << "cnt" << i << ":" << cnt[i] << endl;
  }
  res = 1;
  rep(i, 2, b + 1)
  {
    //cout << i << " " << cnt[i] << " " << modpow(i, cnt[i],MOD) << endl;
    res *= modpow(i, (cnt[i] + MOD) % MOD,MOD);
    res %= MOD;
    // cout << res << endl;
  }
  cout << res << endl;
}

yukicoder

結果

テストケース

ソースコード