結果
問題 | No.2487 Multiple of M |
ユーザー |
![]() |
提出日時 | 2023-09-29 22:38:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,149 bytes |
コンパイル時間 | 1,685 ms |
コンパイル使用メモリ | 169,772 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 06:54:29 |
合計ジャッジ時間 | 3,153 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 8 WA * 45 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll =long long;#define all(v) v.begin(),v.end()#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,a,b) for(int i=a;i>=b;i--)ll INF=2e18;const ll mod = 998244353;class mint {long long x;public:mint(long long x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}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) 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;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};long long GCD(long long a, long long b) {if (b == 0) return a;else return GCD(b, a % b);}ll mod_pow(ll x,ll n,ll mod) {ll res=1;while(n>0) {if(n&1) {res=res*x%mod;}x=x*x%mod;n>>=1;}return res;}int main() {ios::sync_with_stdio(false);cin.tie(0);ll N,M,K;cin>>N>>M>>K;N--;ll n,m;if(N%2==0) {n=N/2;m=N/2;}else {n=(N+1)/2;m=(N-1)/2;}mint k=1;k/=((M-1)*(M-1)-1);ll t=mod_pow((M-1)*(M-1),n,mod);k*=(t-1);mint a=(M-1);a/=((M-1)*(M-1)-1);t=mod_pow((M-1)*(M-1),m,mod);a*=(t-1);mint ans=0;if(N%2==0) ans=a-k;else ans=k-a;ll g=GCD(M,K);ans*=g;ans*=(M-1);cout<<ans<<endl;}