結果

問題 No.2954 Calculation of Exponentiation
ユーザー KumaTachiRenKumaTachiRen
提出日時 2024-11-08 21:36:45
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 25,852 bytes
コンパイル時間 8,900 ms
コンパイル使用メモリ 168,256 KB
実行使用メモリ 192,144 KB
最終ジャッジ日時 2024-11-08 21:37:01
合計ジャッジ時間 12,119 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
32,768 KB
testcase_01 AC 60 ms
29,056 KB
testcase_02 AC 77 ms
33,024 KB
testcase_03 AC 79 ms
32,640 KB
testcase_04 AC 76 ms
32,768 KB
testcase_05 AC 76 ms
32,640 KB
testcase_06 AC 77 ms
32,896 KB
testcase_07 AC 84 ms
32,896 KB
testcase_08 AC 75 ms
32,724 KB
testcase_09 AC 76 ms
32,896 KB
testcase_10 AC 76 ms
32,640 KB
testcase_11 AC 76 ms
32,896 KB
testcase_12 AC 75 ms
33,152 KB
testcase_13 AC 59 ms
29,032 KB
testcase_14 AC 59 ms
28,800 KB
testcase_15 AC 76 ms
32,512 KB
testcase_16 AC 75 ms
32,768 KB
testcase_17 AC 63 ms
29,056 KB
testcase_18 AC 59 ms
29,056 KB
testcase_19 AC 75 ms
32,896 KB
testcase_20 AC 59 ms
29,056 KB
testcase_21 AC 66 ms
29,056 KB
testcase_22 AC 61 ms
28,800 KB
testcase_23 AC 62 ms
28,672 KB
testcase_24 AC 60 ms
29,164 KB
testcase_25 AC 75 ms
32,896 KB
testcase_26 AC 59 ms
28,756 KB
testcase_27 AC 61 ms
28,928 KB
testcase_28 AC 61 ms
29,056 KB
testcase_29 AC 60 ms
28,928 KB
testcase_30 AC 59 ms
192,144 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (101 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(98,3809): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(88,143): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using Lib;
using Lib.MathLib;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using static Lib.Functions;
using static Lib.OutputLib;
public class Solver
{
    const bool MultiTestCase = false;
    void Solve()
    {
        int Read()
        {
            return (int)(rd * 10000);
        }
        long ap = Read(), aq = 10000;
        long bp = Read(), bq = 10000;

        if (bp == 0)
        {
            Yn(true);
            return;
        }
        if (bp < 0)
        {
            (ap, aq) = (aq, ap);
            bp = -bp;
        }

        {
            long g = Gcd(ap, aq);
            ap /= g; aq /= g;
        }
        {
            long g = Gcd(bp, bq);
            bp /= g; bq /= g;
        }

        if (aq != 1) Yn(false);
        else
        {
            var ps = Factorize.PrimeFactors(ap);
            var cnt = new Map<long, int>();
            foreach (var p in ps) cnt[p]++;
            bool ans = true;
            foreach (var p in cnt) ans &= p.Value % bq == 0;
            Yn(ans);
        }
    }

#pragma warning disable CS0162
    public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); }
#pragma warning restore CS0162

    const int IINF = 1 << 30;
    const long INF = 1L << 60;
    int ri { [MethodImpl(256)] get => (int)sc.Integer(); }
    long rl { [MethodImpl(256)] get => sc.Integer(); }
    uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); }
    ulong rul { [MethodImpl(256)] get => sc.UInteger(); }
    double rd { [MethodImpl(256)] get => sc.Double(); }
    string rs { [MethodImpl(256)] get => sc.Scan(); }
    string rline { [MethodImpl(256)] get => sc.Line(); }
    public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
    void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; }
    void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; }
    void ReadArray<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
    void ReadArray<T>(out T[] a, int n, Func<int, T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(i); }
}

static class Program
{
    static public void Main(string[] args)
    {
        SourceExpander.Expander.Expand();
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver();
        Console.Out.Flush();
    }
}
#region Expanded by https://github.com/kzrnm/SourceExpander
public class Map<TKey,TValue>:Dictionary<TKey,TValue>where TKey:notnull{public new TValue this[TKey key]{get{return TryGetValue(key,out TValue?value)?value:default!;}set{if(ContainsKey(key))base[key]=value;else Add(key,value);}}}
namespace Lib{public static class Functions{[MethodImpl(256)]public static int Popcount(ulong x){x=(x&0x5555555555555555UL)+((x>>1)&0x5555555555555555UL);x=(x&0x3333333333333333UL)+((x>>2)&0x3333333333333333UL);x=(x&0x0f0f0f0f0f0f0f0fUL)+((x>>4)&0x0f0f0f0f0f0f0f0fUL);x=(x&0x00ff00ff00ff00ffUL)+((x>>8)&0x00ff00ff00ff00ffUL);x=(x&0x0000ffff0000ffffUL)+((x>>16)&0x0000ffff0000ffffUL);x=(x&0x00000000ffffffffUL)+((x>>32)&0x00000000ffffffffUL);return(int)x;}[MethodImpl(256)]public static int Popcount(long x){x=(x&0x5555555555555555L)+((x>>1)&0x5555555555555555L);x=(x&0x3333333333333333L)+((x>>2)&0x3333333333333333L);x=(x&0x0f0f0f0f0f0f0f0fL)+((x>>4)&0x0f0f0f0f0f0f0f0fL);x=(x&0x00ff00ff00ff00ffL)+((x>>8)&0x00ff00ff00ff00ffL);x=(x&0x0000ffff0000ffffL)+((x>>16)&0x0000ffff0000ffffL);x=(x&0x00000000ffffffffL)+((x>>32)&0x00000000ffffffffL);return(int)x;}[MethodImpl(256)]public static int Popcount(int x){x=(x&0x55555555)+((x>>1)&0x55555555);x=(x&0x33333333)+((x>>2)&0x33333333);x=(x&0x0f0f0f0f)+((x>>4)&0x0f0f0f0f);x=(x&0x00ff00ff)+((x>>8)&0x00ff00ff);x=(x&0x0000ffff)+((x>>16)&0x0000ffff);return x;}[MethodImpl(256)]public static int Ctz(long x){if(x==0)return-1;return Popcount((ulong)((x&-x)-1));}[MethodImpl(256)]public static int CeilPow2(int n){int x=0;while((1<<x)<n)x++;return x;}[MethodImpl(256)]public static int SafeMod(int x,int m){int r=x%m;return r<0?r+Math.Abs(m):r;}[MethodImpl(256)]public static long SafeMod(long x,long m){long r=x%m;return r<0?r+Math.Abs(m):r;}[MethodImpl(256)]public static bool IsIncreasing(long a,long b,long c)=>a<=b&&b<=c;[MethodImpl(256)]public static int Sign(long x)=>x==0?0:(x<0?-1:1);[MethodImpl(256)]public static int Sign(double x)=>x==0?0:(x<0?-1:1);[MethodImpl(256)]public static int DigitSum(long n,int d=10){long s=0;while(n>0){s+=n%d;n/=d;}return(int)s;}[MethodImpl(256)]public static long Floor(long a,long b)=>a>=0?a/b:(a+1)/b-1;[MethodImpl(256)]public static long Ceil(long a,long b)=>a>0?(a-1)/b+1:a/b;[MethodImpl(256)]public static long Gcd(long a,long b){if(a==0)return Math.Abs(b);if(b==0)return Math.Abs(a);if(a<0)a=-a;if(b<0)b=-b;int u=BitOperations.TrailingZeroCount(a);int v=BitOperations.TrailingZeroCount(b);a>>=u;b>>=v;while(a!=b){if(a<b)(a,b)=(b,a);a-=b;a>>=BitOperations.TrailingZeroCount(a);}return a<<Math.Min(u,v);}[MethodImpl(256)]public static(long x,long y,long g)ExtGcd(long a,long b){if(b==0)return(Sign(a),0,Math.Abs(a));long c=SafeMod(a,b);var(x2,y2,g)=ExtGcd(b,c);long x=SafeMod(y2,b);long y=(g-a*x)/b;return(x,y,g);}[MethodImpl(256)]public static void Swap(ref int x,ref int y){x^=y;y^=x;x^=y;}[MethodImpl(256)]public static void Swap(ref long x,ref long y){x^=y;y^=x;x^=y;}[MethodImpl(256)]public static void Swap<T>(ref T x,ref T y){T t=y;y=x;x=t;}[MethodImpl(256)]public static T Clamp<T>(T x,T l,T r)where T:IComparable<T> =>x.CompareTo(l)<=0?l:(x.CompareTo(r)<=0?x:r);[MethodImpl(256)]public static T Clamp<T>(ref T x,T l,T r)where T:IComparable<T> =>x=x.CompareTo(l)<=0?l:(x.CompareTo(r)<=0?x:r);[MethodImpl(256)]public static void Chmin<T>(ref T x,T y)where T:IComparable<T>{if(x.CompareTo(y)>0)x=y;}[MethodImpl(256)]public static void Chmax<T>(ref T x,T y)where T:IComparable<T>{if(x.CompareTo(y)<0)x=y;}[MethodImpl(256)]public static int LowerBound(long[]arr,long val,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),t=>Sign(t-val),l,r);[MethodImpl(256)]public static int LowerBound(int[]arr,int val,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),t=>t-val,l,r);[MethodImpl(256)]public static int LowerBound<T>(T[]arr,T val,int l=-1,int r=-1)where T:IComparable<T> =>LowerBound(arr.AsSpan(),t=>t.CompareTo(val),l,r);[MethodImpl(256)]public static int LowerBound<T>(T[]arr,Func<T,int>comp,int l=-1,int r=-1)=>LowerBound(arr.AsSpan(),comp,l,r);[MethodImpl(256)]public static int LowerBound<T>(Span<T>data,Func<T,int>comp,int l=-1,int r=-1){if(data.Length==0)return-1;if(l==-1)l=0;if(r==-1)r=data.Length;while(l<r){int x=(l+r)/2;if(comp(data[x])<0)l=x+1;else r=x;}return l;}[MethodImpl(256)]public static int RangeCount<T>(T[]arr,T geq,T lt,int l=-1,int r=-1)where T:IComparable<T> =>Math.Max(0,LowerBound(arr.AsSpan(),t=>t.CompareTo(lt),l,r)-LowerBound(arr.AsSpan(),t=>t.CompareTo(geq),l,r));[MethodImpl(256)]public static string ToBase2(long v,int digit=-1){if(digit==-1){digit=0;while((v>>digit)>0)digit++;}var c=new string[digit];for(int i=0;i<digit;i++)c[digit-1-i]=((v>>i)&1)==0?"0":"1";return string.Join("",c);}[MethodImpl(256)]public static string ToBaseN(long v,int n,int digit=-1){if(digit==-1){digit=0;long pow=1;while(v>=pow){digit++;pow*=n;}}var c=new int[digit];for(int i=0;i<digit;i++,v/=n)c[digit-1-i]=(int)(v%n);return string.Join("",c);}}}
public interface IField<T>where T:IField<T>{public static abstract T operator-(T x);public static abstract T operator+(T l,T r);public static abstract T operator-(T l,T r);public static abstract T operator*(T l,T r);public static abstract T operator/(T l,T r);public static abstract T Zero{get;}public static abstract T One{get;}public static abstract bool IsZero(T x);public static abstract bool IsOne(T x);}
namespace Lib{public partial class StreamScanner{public StreamScanner(Stream stream){str=stream;}private readonly Stream str;private readonly byte[]buf=new byte[1024];private int len,ptr;public bool isEof=false;public bool IsEndOfStream{get{return isEof;}}[MethodImpl(256)]private byte Read(){if(isEof)throw new EndOfStreamException();if(ptr>=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++];}[MethodImpl(256)]public char Char(){byte b;do b=Read();while(b<33||126<b);return(char)b;}[MethodImpl(256)]public string Line(){var sb=new StringBuilder();for(var b=Char();b!=10&&!isEof;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public string Scan(){var sb=new StringBuilder();for(var b=Char();b>=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;var ng=false;byte b;do b=Read();while(b!='-'&&(b<'0'||'9'<b));if(b=='-'){ng=true;b=Read();}for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(b^'0');return ng?-ret:ret;}[MethodImpl(256)]public ulong UInteger(){ulong ret=0;byte b;do b=Read();while(b<'0'||'9'<b);for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(ulong)(b^'0');return ret;}[MethodImpl(256)]public double Double()=>double.Parse(Scan());}}
namespace Lib.MathLib{public class BigMontgomery{private readonly ulong n,r2,nInv;public readonly ulong One,MinusOne;public BigMontgomery(ulong n){ulong r2=1;for(int i=0;i<64;i++)r2=(r2<<1)>=n?(r2<<1)-n:(r2<<1);One=r2;MinusOne=One==0?0:n-One;for(int i=0;i<64;i++)r2=(r2<<1)>=n?(r2<<1)-n:(r2<<1);ulong nInv=n;for(int i=0;i<5;++i)nInv*=2-n*nInv;this.n=n;this.r2=r2;this.nInv=nInv;}[MethodImpl(256)]private static ulong High(ulong x,ulong y){ulong xl=x&0xffffffffUL;ulong xh=x>>32;ulong yl=y&0xffffffffUL;ulong yh=y>>32;ulong k=(((xh*yl)&0xffffffffUL)+((xl*yh)&0xffffffffUL)+(xl*yl>>32))>>32;return xh*yh+(xh*yl>>32)+(xl*yh>>32)+k;}[MethodImpl(256)]private static bool Carry(ulong x,ulong y){ulong v=(x>>1)+(y>>1);return(((v+(x&y&1))>>63)&1)==1;}[MethodImpl(256)]public ulong Reduct(ulong x){ulong z=unchecked(0ul-nInv)*x;ulong res=High(z,n);if(Carry(z*n,x))res++;if(res>=n)res-=n;return res;}[MethodImpl(256)]public ulong Transform(ulong x)=>MRMul(x,r2);[MethodImpl(256)]public ulong MRMul(ulong x,ulong y){ulong u=High(x,y);ulong d=Reduct(x*y);ulong z=u+d;if(z>=n)z-=n;return z;}[MethodImpl(256)]public ulong Mul(ulong x,ulong y){ulong z=High(x,y)+Reduct(x*y);if(z>=n)z-=n;z=High(z,r2)+Reduct(z*r2);if(z>=n)z-=n;return z;}[MethodImpl(256)]public ulong Pow(ulong x,ulong n){x=Transform(x);ulong r=One;while(n>0){if(n%2==1)r=MRMul(r,x);x=MRMul(x,x);n/=2;}return Reduct(r);}}}
namespace Lib.MathLib{public static class Factorize{const int SMALL_PRIMES_MAX=257;static readonly byte[]SMALL_PRIMES=new byte[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251};static Dictionary<long,long[]>cache_factors;public static long[]PrimeFactors(long n){var ps=Calc(n);Array.Sort(ps);return ps;}public static IEnumerable<long>EnumerateFactors(long n)=>Calc(n);[MethodImpl(256)]private static long[]Calc(long n){cache_factors??=new Dictionary<long,long[]>();if(cache_factors.TryGetValue(n,out var r))return r;int sz=BitOperations.TrailingZeroCount(n);if(sz==0){r=CalcMain(n);}else{var q=CalcMain(n>>sz);r=new long[q.Length+sz];r.AsSpan(0,sz).Fill(2);q.AsSpan().CopyTo(r.AsSpan(sz));}cache_factors.Add(n,r);return r;}[MethodImpl(256)]private static long[]CalcMain(long n){if(n==1)return Array.Empty<long>();if(n<SMALL_PRIMES_MAX*SMALL_PRIMES_MAX){Span<long>buf=stackalloc long[16];int sz=0;foreach(var p in SMALL_PRIMES)for(;n%p==0;n/=p)buf[sz++]=p;if(n>1)buf[sz++]=n;return buf[..sz].ToArray();}else{long p=n;if(n<(1L<<30)){p=PollardRho32((uint)n);}else if(n<(1L<<62)){p=PollardRho64((ulong)n);}if(p==n)return new long[]{n};var a=Calc(p);var b=Calc(n/p);Span<long>buf=stackalloc long[a.Length+b.Length];a.AsSpan().CopyTo(buf);b.AsSpan().CopyTo(buf[a.Length..]);return buf.ToArray();}}[MethodImpl(256)]private static uint PollardRho32(uint n){if((n&1)==0)return 2;if(MillerRabin.IsPrime(n))return n;var bar=new Barrett(n);for(uint c=1;;c++){uint x=c;uint y=bar.Mul(x,x)+c;if(y>=n)y-=n;for(int t=0;t<100000;t++){uint d=x<y?y-x:x-y;if(d==0)break;uint g=FastGCD.Gcd(d,n);if(g!=1)return g;x=bar.Mul(x,x)+c;if(x>=n)x-=n;y=bar.Mul(y,y)+c;if(y>=n)y-=n;y=bar.Mul(y,y)+c;if(y>=n)y-=n;}}}[MethodImpl(256)]private static long PollardRho64(ulong n){if((n&1)==0)return 2;if(MillerRabin.IsPrime(n))return(long)n;var mont=new BigMontgomery(n);for(uint c=1;;c++){ulong cr=mont.Transform(c);ulong x=cr;ulong y=mont.MRMul(x,x)+cr;if(y>=n)y-=n;ulong prod=mont.One,px=x,py=y;for(int t=1;t<=100000;t++){ulong d=x>y?x-y:y-x;if(d==0)break;prod=mont.MRMul(prod,d);if((t&0b11)==0){ulong g=FastGCD.Gcd(mont.Reduct(d),n);if(g!=1){x=px;y=py;while(true){d=x>y?x-y:y-x;g=FastGCD.Gcd(mont.Reduct(d),n);if(g!=1)return(long)g;x=mont.MRMul(x,x)+cr;if(x>=n)x-=n;y=mont.MRMul(y,y)+cr;if(y>=n)y-=n;y=mont.MRMul(y,y)+cr;if(y>=n)y-=n;}}prod=1;px=x;py=y;}x=mont.MRMul(x,x)+cr;if(x>=n)x-=n;y=mont.MRMul(y,y)+cr;if(y>=n)y-=n;y=mont.MRMul(y,y)+cr;if(y>=n)y-=n;}}}}}
namespace Lib.MathLib{public static class FastGCD{public static uint Gcd(uint a,uint b){if(a==0)return b;if(b==0)return a;int u=BitOperations.TrailingZeroCount(a);int v=BitOperations.TrailingZeroCount(b);a>>=u;b>>=v;while(a!=b){if(a<b)(a,b)=(b,a);a-=b;a>>=BitOperations.TrailingZeroCount(a);}return a<<Math.Min(u,v);}public static ulong Gcd(ulong a,ulong b){if(a==0)return b;if(b==0)return a;int u=BitOperations.TrailingZeroCount(a);int v=BitOperations.TrailingZeroCount(b);a>>=u;b>>=v;while(a!=b){if(a<b)(a,b)=(b,a);a-=b;a>>=BitOperations.TrailingZeroCount(a);}return a<<Math.Min(u,v);}}}namespace Lib.MathLib{public static class FastGCD<T>where T:IBinaryInteger<T>{public static T Gcd(T a,T b){if(T.IsZero(a))return T.Abs(b);if(T.IsZero(b))return T.Abs(a);if(T.IsNegative(a))a=-a;if(T.IsNegative(b))b=-b;int u=int.CreateChecked(T.TrailingZeroCount(a));int v=int.CreateChecked(T.TrailingZeroCount(b));a>>=u;b>>=v;while(a!=b){if(a<b)(a,b)=(b,a);a-=b;a>>=int.CreateChecked(T.TrailingZeroCount(a));}return a<<Math.Min(u,v);}public static T Lcm(T a,T b)=>a/Gcd(a,b)*b;}}
namespace Lib{public class Barrett{public readonly uint Mod;public readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[MethodImpl(256)]public uint Mul(uint a,uint b)=>Reduce((ulong)a*b);[MethodImpl(256)]public uint Reduce(ulong z){var x=InternalMath.Mul128Bit(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}[MethodImpl(256)]public uint Pow(long x,long n){if(Mod==1)return 0;uint r=1,y=(uint)InternalMath.SafeMod(x,Mod);while(n>0){if((n&1)!=0)r=Mul(r,y);y=Mul(y,y);n>>=1;}return r;}}}
namespace Lib{public static class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[MethodImpl(256)]public static int PrimitiveRoot<TMod>()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate<TMod>();}static int PrimitiveRootCalculate<TMod>()where TMod:struct,IStaticMod{var m=default(TMod).Mod;Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt<TMod>(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:;}}[MethodImpl(256)]public static int PrimitiveRoot(uint m){if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate(m);}static int PrimitiveRootCalculate(uint m){Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);uint Pow(uint x,uint n){uint y=1;while(n>0){if((n&1)==1)y=y*x%m;x=x*x%m;n/=2;}return y;}for(uint g=2;;g++){foreach(var d in divs)if(Pow(g,(m-1)/d)==1)goto NEXT;return(int)g;NEXT:;}}[MethodImpl(256)]public static(long,long)InvGcd(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}[MethodImpl(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[MethodImpl(256)]public static bool IsPrime(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long d=n-1;while(d%2==0)d/=2;ReadOnlySpan<byte>bases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}[MethodImpl(256)]public static uint PowMod(long x,long n,int m){if(m==1)return 0;return new Barrett((uint)m).Pow(x,n);}[MethodImpl(256)]public static uint PowMod(long x,long n,uint m){if(m==1)return 0;return new Barrett(m).Pow(x,n);}[MethodImpl(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax<m)return ans;(n,m,a,b)=(yMax/m,a,m,yMax%m);}}[MethodImpl(256)]public static ulong Mul128Bit(ulong a,ulong b){if(System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)return System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(a,b);return Mul128BitLogic(a,b);}[MethodImpl(256)]internal static ulong Mul128BitLogic(ulong a,ulong b){var au=a>>32;var ad=a&0xFFFFFFFF;var bu=b>>32;var bd=b&0xFFFFFFFF;var l=ad*bd;var m1=au*bd;var m2=ad*bu;var h=au*bu;var lu=l>>32;var m1d=m1&0xFFFFFFFF;var m2d=m2&0xFFFFFFFF;var c=m1d+m2d+lu;return h+(m1>>32)+(m2>>32)+(c>>32);}}}
namespace Lib.MathLib{public static class MillerRabin{const int SMALL_PRIMES_MAX=257;static readonly byte[]SMALL_PRIMES=new byte[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251};[MethodImpl(256)]static bool Calc32(uint n,ReadOnlySpan<uint>ws){if(n<=2)return n==2;if(n%2==0)return false;int l=BitOperations.TrailingZeroCount(n-1);uint d=(n-1)>>l;var prod=true;foreach(var w in ws){if(w%n==0)continue;ulong y=Pow(w,d,n);if(y!=1){bool maybe_prime=false;for(int i=0;i<l;i++){if(y==n-1){maybe_prime=true;break;}y=y*y%n;}prod&=maybe_prime;}}return prod;}[MethodImpl(256)]static bool Calc64(ulong n,ReadOnlySpan<ulong>ws){if(n<=2)return n==2;if(n%2==0)return false;var mont=new BigMontgomery(n);int l=BitOperations.TrailingZeroCount(n-1);ulong d=(n-1)>>l;while((d&1)==0)d>>=1;var prod=true;ulong minus1=mont.Transform(n-1);foreach(var w in ws){if(n<=w)continue;ulong y=mont.Pow(w,d);if(y!=1){y=mont.Transform(y);bool maybe_prime=false;for(int i=0;i<l;i++){if(y==minus1){maybe_prime=true;break;}y=mont.MRMul(y,y);}prod&=maybe_prime;}}return prod;}[MethodImpl(256)]static uint Pow(uint a,uint n,uint m){ulong x=a%m,y=1;while(n>0){if((n&1)==1)y=y*x%m;x=x*x%m;n>>=1;}return(uint)y;}[MethodImpl(256)]public static bool IsPrime(ulong n){if(n<=2)return n==2;if(n%2==0)return false;return IsPrimeInner(n);}[MethodImpl(256)]private static bool IsPrimeInner(ulong n){if(n<SMALL_PRIMES_MAX*SMALL_PRIMES_MAX){foreach(var p in SMALL_PRIMES){if(n==p)return true;else if(n%p==0)return false;}return true;}else if(n<(1UL<<30)){return Calc32((uint)n,stackalloc uint[]{2,7,61});}else if(n<(1UL<<62)){return Calc64(n,stackalloc ulong[]{2,325,9375,28178,450775,9780504,1795265022});}return false;}}}
namespace Lib{public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}public readonly struct StaticModInt<T>:IEquatable<StaticModInt<T>>,IField<StaticModInt<T>>where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;public static StaticModInt<T>Zero=>default;public static StaticModInt<T>One=>new StaticModInt<T>(1u);[MethodImpl(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}[MethodImpl(256)]public StaticModInt(long v):this(Round(v)){}[MethodImpl(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[MethodImpl(256)]private StaticModInt(uint v)=>_v=v;public static bool IsZero(StaticModInt<T>x)=>x.Value==0;public static bool IsOne(StaticModInt<T>x)=>x.Value==1;[MethodImpl(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0)x+=op.Mod;return(uint)x;}[MethodImpl(256)]public static StaticModInt<T>operator ++(StaticModInt<T>v){var x=v._v+1;if(x==op.Mod)x=0;return new StaticModInt<T>(x);}[MethodImpl(256)]public static StaticModInt<T>operator --(StaticModInt<T>v){var x=v._v;if(x==0)x=op.Mod;return new StaticModInt<T>(x-1);}[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>lhs,StaticModInt<T>rhs){var v=lhs._v+rhs._v;if(v>=op.Mod)v-=op.Mod;return new StaticModInt<T>(v);}[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>lhs,StaticModInt<T>rhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod)v+=op.Mod;return new StaticModInt<T>(v);}}[MethodImpl(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*Inv(rhs._v)%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>v)=>v;[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>v)=>new StaticModInt<T>(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt<T>(int v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(uint v)=>new StaticModInt<T>((long)v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(long v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(ulong v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator long(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public static implicit operator ulong(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);if(n<0)(x,n)=(x.Inv(),-n);while(n>0){if((n&1)>0)r*=x;x*=x;n>>=1;}return r;}[MethodImpl(256)]public StaticModInt<T>Inv()=>new StaticModInt<T>(Inv(_v));[MethodImpl(256)]static ulong Inv(ulong x){long u=op.Mod,xu=1,yu=0,v=(long)x,xv=0,yv=1;while(v!=0){long w=SafeMod(u,v);long q=(u-w)/v;long xw=xu-xv*q;long yw=yu-yv*q;u=v;xu=xv;yu=yv;v=w;xv=xw;yv=yw;}return(ulong)(yu<0?yu+op.Mod:yu);}[MethodImpl(256)]static long SafeMod(long x,long m){long r=x%m;if(r<0)r+=m;return r;}[MethodImpl(256)]public override string ToString()=>_v.ToString();[MethodImpl(256)]public string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);[MethodImpl(256)]public override bool Equals(object?obj)=>obj is StaticModInt<T>m&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;[MethodImpl(256)]public override int GetHashCode()=>_v.GetHashCode();}}
namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin<T>(string s,IEnumerable<T>t)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat<T>(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i<sz1;i++){for(int j=0;j<sz2;j++)b[j]=a[i,j];WriteJoin(sep,b);}}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,string sep=" "){foreach(var ar in a)WriteJoin(sep,ar);}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,Func<T,string>map,string sep=" "){foreach(var ar in a)WriteJoin(sep,ar.Select(x=>map(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write(string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn(bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x=(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat("_",blocks-x))}] : {now} / {total}");}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0