結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2021-01-22 22:47:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 490 ms / 2,000 ms |
コード長 | 3,361 bytes |
コンパイル時間 | 2,455 ms |
コンパイル使用メモリ | 174,168 KB |
実行使用メモリ | 7,244 KB |
最終ジャッジ日時 | 2024-12-28 04:30:27 |
合計ジャッジ時間 | 5,709 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2021.01.22 22:45:04**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template< int MOD >struct mint {public:long long x;mint(long long x = 0) :x((x%MOD+MOD)%MOD) {}mint(std::string &s) {long long z = 0;for (int i = 0; i < s.size(); i++) {z *= 10;z += s[i] - '0';z %= MOD;}this->x = z;}mint& operator+=(const mint &a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint& operator-=(const mint &a) {if ((x += MOD - a.x) >= MOD) x -= MOD;return *this;}mint& operator*=(const mint &a) {(x *= a.x) %= MOD;return *this;}mint& operator/=(const mint &a) {long long n = MOD - 2;mint u = 1, b = a;while (n > 0) {if (n & 1) {u *= b;}b *= b;n >>= 1;}return *this *= u;}mint operator+(const mint &a) const {mint res(*this);return res += a;}mint operator-() const {return mint() -= *this; }mint operator-(const mint &a) const {mint res(*this);return res -= a;}mint operator*(const mint &a) const {mint res(*this);return res *= a;}mint operator/(const mint &a) const {mint res(*this);return res /= a;}friend std::ostream& operator<<(std::ostream &os, const mint &n) {return os << n.x;}friend std::istream &operator>>(std::istream &is, mint &n) {long long x;is >> x;n = mint(x);return is;}bool operator==(const mint &a) const {return this->x == a.x;}bool operator!=(const mint &a) const {return this->x != a.x;}mint pow(long long k) const {mint ret = 1;mint p = this->x;while (k > 0) {if (k & 1) {ret *= p;}p *= p;k >>= 1;}return ret;}};constexpr int MOD = 1e9 + 7;vector< int > euler_phi(int n) {vector< int > euler(n + 1);for(int i = 0; i <= n; i++) {euler[i] = i;}for(int i = 2; i <= n; i++) {if(euler[i] == i) {for(int j = i; j <= n; j += i) {euler[j] = euler[j] / i * (i - 1);}}}return euler;}ll powMod(ll k, ll n, ll mod) {ll x = 1;while (n > 0) {if (n & 1) {x = x * k % mod;}k = k * k % mod;n >>= 1;}return x;}int main() {int t;cin >> t;auto phi = euler_phi(1000000);while(t--) {vector<ll> a(3);for (int i = 0; i < 3; i++) {cin >> a[i];}ll y;cin >> y;sort(a.rbegin(), a.rend());ll g = __gcd(a[1],a[2]);a[1] /= g;a[2] /= g;mint<MOD> ans = 0;ll pm = powMod(a[1],phi[a[2]]-1,a[2]);for (int i = 0; i*a[0] <= y; i++) {ll x = y-i*a[0];if (x % g != 0) continue;x /= g;ll z = pm * x % a[2];if (z > x/a[1]) continue;ans += (x/a[1]-z)/a[2]+1;}cout << ans << endl;}return 0;}