#1177867 (C++23(gcc16)) No.3577 フェルマー曲線

• 問題: No.3577 フェルマー曲線
• ユーザー: khasu329
• 提出日時: 2026-08-21 16:12:10
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 92 ms / 4,000 ms
• コード長: 14,094 bytes
• コンパイル時間: 4,229 ms
• コンパイル使用メモリ: 392,752 KB
• 実行使用メモリ: 9,388 KB
• 最終ジャッジ日時: 2026-08-21 16:12:18
• 合計ジャッジ時間: 7,064 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

ファイルパターン	結果
other	AC * 24

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

#define LOGICAL_SUB1(name,expr) [&](const auto& name){return expr;}
#define LOGICAL_SUB2(expr) [&](const auto& arg){return expr;}
#define LOGICAL_SUB0(_1,_2,_3,...) _3
#define LOGICAL(...) LOGICAL_SUB0(__VA_ARGS__,LOGICAL_SUB1,LOGICAL_SUB2)(__VA_ARGS__)
#define CONCAT(a,b) a ## b
#define VAR_CONCAT(p) CONCAT(p,__LINE__)
#define LOOP(n) for(long long VAR_CONCAT(VAR)=0;VAR_CONCAT(VAR)<n;VAR_CONCAT(VAR)++)
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define REP(i,a,n) for(long long i = (long long)(a); i< (n); i++)
#define rrep(i,n) for(long long i = (long long)(n)-1LL;i>=0; i--)//n-1から0のループ
#define RREP(i,a,n) for(long long i = (long long)(a)-1LL;i>=(long long)(n); i--)
#define repp(i,n) for(long long i= (long long)n;i>=0LL;i--)
#define REPP(i,a,n) for(long long i = (a);i>=(long long)(n);i--)
#define fore(x,a) for(auto (x):(a))
#define FORE(x,a) for(auto& (x):(a))
#define dwhile(a) while(!(a))//わかりやすいだけ
#define all(x) x.begin(), x.end()
#define Yes cout << "Yes" << '\n'
#define No cout << "No" << '\n'
#define YES cout << "YES" << '\n'
#define NO cout << "NO" << '\n'
#define yn(b) if(b){Yes;}else{No;}
#define YN(b) if(b){YES;}else{NO;}
#define rsort(i) sort(i);reverse(i)
#define UNIQUE(n) n.erase(unique(all(n)),n.end())
#define dump(...) cout << __LINE__ << ":[" << #__VA_ARGS__ << "]: ";println(__VA_ARGS__);
namespace others{
//https://qiita.com/hibit/items/8ca9a58ccd23014f3a54#%E5%85%A8%E9%83%A8%E3%81%BE%E3%81%A8%E3%82%81%E3%81%A6
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << "(" << p.first << "," << p.second << ")";
    return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p)
{
    is >> p.first >> p.second;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << endl;
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << "i = " << i << endl;
        os << v[i];
    }
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (T &in : v)
        is >> in;
    return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp)
{
    for (auto &[key, val] : mp)
    {
        os << key << ":" << val << " ";
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, queue<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop();
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, deque<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop_front();
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, stack<T> st)
{
    while (st.size())
    {
        os << st.top() << " ";
        st.pop();
    }
    return os;
}
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq)
{
    while (pq.size())
    {
        os << pq.top() << " ";
        pq.pop();
    }
    return os;
}
//vector
template<typename T>
T vmax(vector<T>& n){
  T mx=n[0];
  rep(i,n.size()){
    if(mx<n[i]){
      mx=n[i];
    }
  }return mx;
}template<typename T>
T vmin(vector<T>& n){
  T mn=n[0];
  rep(i,n.size()){
    if(mn>n[i]){
      mn=n[i];
    }
  }return mn;
}
//pair
template<typename T,typename S>
pair<T,S> operator+(const pair<T,S>&l,const pair<T,S>&r){
  return{l.first+r.first,l.second+r.second};
}template<typename T,typename S>
pair<T,S> operator-(const pair<T,S>&l,const pair<T,S>&r){
  return{l.first-r.first,l.second-r.second};
}template<typename T,typename S>
pair<T,S> operator*(const pair<T,S>&l,const pair<T,S>&r){
  return{l.first*r.first,l.second*r.second};
}template<typename T,typename S>
pair<T,S> operator/(const pair<T,S>&l,const pair<T,S>&r){
  return{l.first/r.first,l.second/r.second};
}template<typename T,typename S>
pair<T,S> operator%(const pair<T,S>&l,const pair<T,S>&r){
  return{l.first%r.first,l.second%r.second};
}template<typename T,typename S>
pair<T,S>& operator+=(pair<T,S>&l,const pair<T,S>&r){
  l.first+=r.first;
  l.second+=r.second;
  return l;
}template<typename T,typename S>
pair<T,S>& operator-=(pair<T,S>&l,const pair<T,S>&r){
  l.first-=r.first;
  l.second-=r.second;
  return l;
}template<typename T,typename S>
pair<T,S>& operator*=(pair<T,S>&l,const pair<T,S>&r){
  l.first*=r.first;
  l.second*=r.second;
  return l;
}template<typename T,typename S>
pair<T,S>& operator/=(pair<T,S>&l,const pair<T,S>&r){
  l.first/=r.first;
  l.second/=r.second;
  return l;
}template<typename T,typename S>
pair<T,S>& operator%=(pair<T,S>&l,const pair<T,S>&r){
  l.first%=r.first;
  l.second%=r.second;
  return l;
}
}
using namespace others;
template<typename T,typename U> using umap = unordered_map<T,U>;
template<typename T> using uset = unordered_set<T>;
using uint = unsigned int;
using ull = unsigned long long;
using ll = long long;
using pll = pair<ll,ll>;
using vpl = vector<pair<ll,ll>>;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T>>;
template<typename T> using vvv = v<vv<T>>;
using vl = v<ll>;
using vvl = vv<ll>;
using vvvl = vvv<ll>;
using vs = v<string>;
using vvs = vv<string>;
using vvvs = vvv<string>;
using Graph = vv<int>;
using Tree = vv<int>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using pq_g = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const string abc = "abcdefghijklmnopqrstuvwxyz";
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const v<ll> dx={1,0,-1,0,1,1,-1,-1};
const v<ll> dy={0,1,0,-1,1,-1,1,-1};
const ll INF = 2e18;
const double pi = 3.1415926535897932384626;
namespace my_library{
  namespace lib_of_graph{
    template<typename T>
    v<T> topological_sort(vv<T>& g){
      ll N=ll(g.size());
      v<T> ret(0);
      v<T> n(N);
      queue<T> BFS;
      rep(i,N){
        for(T x:g[i]){
          n[x]++;
        }
      }rep(i,N){
        if(n[i]==0){
          ret.push_back(i);
          BFS.push(i);
        }
      }while(BFS.size()>0){
        for(T x:g[BFS.front()]){
          n[x]--;
          if(n[x]==0){
            ret.push_back(x);
            BFS.push(x);
          }
        }BFS.pop();
      }return ret;
    }
  }
  namespace base{
    template<typename T,typename U,typename V>ll tousa_sum(T a,U b,V c){//初項,交差,項数
      return (b*(c-1)+a*2)*c/2;
    }template<typename T>vector<T> get_rank(vector<T> A){
      ll r=0;
      map<ll,ll> taiou;
      sort(all(A));
      rep(i,A.size()){
        r++;
        if(i>0&&A[i]==A[i-1]){
          r--;
        }taiou[A[i]]=r;
      }rep(i,A.size()){
        A[i]=taiou[A[i]];
      }
      return A;
    }
    template<typename T,typename U>
    string to_baseN(T base,U N){
      if(N==0){
        return "0";
      }
      string ret="";
      while(N>0){
        ret+='0'+N%base;
        N/=base;
      }reverse(all(ret));
      return ret;
    }template<typename T>
    ll to_baseten(T a,string S){
      ll k=1,ret=0;
      reverse(all(S));
      rep(i,S.size()){
        ret+=k*(S[i]-'0');
        k*=a;
      }return ret;
    }template<typename T,typename U>
    bool in(U a,T b, T c){//おそらく半開区間
      return a<=b&&b<c;
    }template<typename T>
    bool in_grid(T H,T W,T a,T b){
      return(in(0,a,H)&&in(0,b,W));
    }
  }
  namespace data_struct{
    template<typename T>
    struct BIT{
      int N;
      vector<T> bit;
      function<T(T,T)> op=[](T a,T b){return a+b;};
      function<T(T,T)> inv_op=[](T a,T b){return a-b;};
      BIT(int n):N(n+1),bit(n+1,T()){}
      template<typename F,typename G>
      BIT(int n,F operator_,G inv_operator_):N(n+1),bit(n+1,T()),op(operator_),inv_op(inv_operator_){}
      void add(int a,T b){//a番目にbを加算。0≦a<N
        a++;
        for(int i=a;i<N;i+=(i&-i)){
          bit[i]=op(bit[i],b);
        }
        return;
      }
      T sum(int a,int b){//[a,b)の和
        T ret=T();
        for(int i=a;i>0;i-=(i&-i)){
          ret=inv_op(ret,bit[i]);
        }for(int i=b;i>0;i-=(i&-i)){
          ret=op(ret,bit[i]);
        }return ret;
      }int lower_bound(T a){
        int idx=0,r=1;
        while(N>r)r*=2;
        for(int len=r;len>0;len=len>>1){
          if(idx+len<N&&bit[idx+len]<a){
            a=inv_op(a,bit[idx+len]);
            idx+=len;
          }
        }return idx;
      }int upper_bound(T a){
        int idx=0,r=1;
        while(N>r)r*=2;
        for(int len=r;len>0;len=len>>1){
          if(idx+len<N&&bit[idx+len]<=a){
            a=inv_op(a,bit[idx+len]);
            idx+=len;
          }
        }return idx;
      }
    };
  }
  namespace math{
    struct prime{
      vl isprime;
      vl minfactor;
      prime(ll N):isprime(N+1,true),minfactor(N+1,1){
        isprime[1]=false;
        for(ll i=1;i<N+1;i++){
          if(isprime[i]){
            for(int j=2*i;j<N+1;j+=i){
              isprime[j]=false;
              if(minfactor[j]==1){
                minfactor[j]=i;
              }
            }
          }
        }
      }vpl factorize(ll n){
        vpl ret(0);
        while(n>1){
          ll s=0;
          ll p=minfactor[n];
          if(p==1){
            ret.push_back({n,1});
            break;
          }
          while(n%p==0){
            n/=p;
            s++;
          }
          ret.push_back({p,s});
        }return ret;
      }
    };
    vl prime_fact(ll N,vl prime){
      vl ans(prime.size());
      if(N<=0){
        return ans;
      }
      rep(i,ll(prime.size())){//旧
        while(N%prime[i]==0){
          N/=prime[i];
          ans[i]++;
        }
      }return ans;
    }ll modpow(ll a,ll b){//modはしない。語感
      ll ret=1,tmp=a;
      while(b>0){
        if(b&1){
          ret*=tmp;
        }
        b>>=1;
        tmp*=tmp;
      }return ret;
    }template<int M>
    static_modint<M> modpow(static_modint<M> a,ll b){
      static_modint<M> ret=1,tmp=a;
      while(b>0){
        if(b&1){
          ret*=tmp;
        }
        b>>=1;
        tmp*=tmp;
      }return ret;
    }modint modpow(modint a,ll b){
      modint ret=1,tmp=a;
      while(b>0){
        if(b&1){
          ret*=tmp;
        }
        b>>=1;
        tmp*=tmp;
      }return ret;
    }
  }
  namespace string_algorithm{
    struct RollingHash{//ハッシュ衝突に気を付ける。心配なら2つ別のmodで持っとくといい
      long long int base=3290329LL;
      long long int mod=1000000007LL;
      vector<long long int> hash;
      vector<long long int> power;
      string S;
      RollingHash(const string& s):hash(s.size()+1),power(s.size()+1,1),S(s){
        ll a=0;
        ll bas=1;
        for(long long int i=0;i<(long long int)(s.size());i++){
          a*=base;
          a+=int(s[i]);
          a%=mod;
          hash[i+1]=a;
          bas*=base;
          bas%=mod;
          power[i+1]=bas;
        }
      }
      RollingHash(const string& s,const long long int& b,const long long int& m):base(b),mod(m),hash(s.size()+1),power(s.size()+1,1),S(s){
        ll a=0;
        ll bas=1;
        for(long long int i=0;i<(long long int)(s.size());i++){
          a*=base;
          a+=int(s[i]);
          a%=mod;
          hash[i+1]=a;
          bas*=base;
          bas%=mod;
          power[i+1]=bas;
        }
      }long long int get(int l,int r){
        long long int ret=(hash[r]-(hash[l]*power[r-l])%mod+mod)%mod;
        return ret;
      }
    };
  }namespace IO{
    //入力
    template<typename... T>
    void vin(T&... args){
      ((cin>>args),...);
      return;
    }template<typename T,typename... U>
    void vvin(vector<T>& hd,vector<U>&... args){
      rep(i,(long long int)hd.size()){
        cin >> hd[i];
        ((cin>>args[i]),...);
      }return;
    }
    //出力
    template<typename... T>
    void println(const T&... args){
      ((cout << args << " "),...);
      cout << endl;
    }
  }
}
void DFS(vvl& g,ll p,ll oya){
  /*行く(ついた)ときの処理*/
  for(ll x:g[p]){
    if(x==oya){
      continue;
    }
    DFS(g,x,p);
  }/*帰りの処理*/
}
using namespace my_library::lib_of_graph;
using namespace my_library::base;//旧
using namespace my_library::data_struct;//BITなど
using namespace my_library::math;
using namespace my_library::string_algorithm;
using namespace my_library::IO;
using mint = modint998244353;
void solve(){
  ll N,B,ans=0;
  cin >> N >> B;
  //x,y,zは[0,B)なので、全探索してもO(B^3)
  //半分全列挙の要領でO(B^2)
  //x,yを固定して、zが存在するか調べる
  vl Zm(B);
  modint::set_mod(B);
  modint Zv;
  v<modint> A(B);
  rep(i,B){
    Zv=i;
    Zv=modpow(Zv,N);
    Zm[Zv.val()]++;
    A[i]=Zv;
  }rep(i,B){
    rep(j,B){
      ans+=Zm[(A[i]+A[j]).val()];
    }
  }cout << ans << "\n";
  return;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  ll T=1;
  //cin >> T;
  rep(i,T) solve();
}