• The 2023 ICPC Asia Regionals Online Contest (1) E. Magical Pair（数论 欧拉函数）

    题目

    T(T<=10)组样例，每次给出一个n(2<=n<=1e18)，

    询问多少对(x,y)(0<=x,y<=n^2-n)，满足x^y\equiv y^x(mod \ n)

    答案对998244353取模，保证n-1不是998244353倍数

    思路来源

    OEIS、SSerxhs、官方题解

    2023 ICPC 网络赛 第一场简要题解 - 知乎

    题解

    官方题解还没有补，OEIS打了个表然后就通过了

    这里给一下SSerxhs教的做法吧（图源：我、tanao学弟）

    SSerxhs代码

    我的理解

    首先，证一下这个和\sum_{i=0}^{p-2}b_{i}^2是等价的，其中bi为满足x^y\equiv i的(x,y)的对数

    关于这部分，题解里给的中国剩余定理的构造，也很巧妙

    剩下的部分就很神奇了，首先需要注意到各个素因子的贡献是独立的，可以连积

    对于求某个素因子的幂次的贡献时，用到了解的分布是均匀的性质

    代码1（OEIS）

    1. #include
    2. using namespace std;
    3. #define In inline
    4. typedef long long ll;
    5. typedef double db;
    6. const int INF = 0x3f3f3f3f;
    7. const db eps = 1e-8;
    8. mapans;
    9. inline ll read()
    10. {
    11.     ll ans = 0;
    12.     char ch = getchar(), last = ' ';
    13.     while(!isdigit(ch)) {last = ch; ch = getchar();}
    14.     while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}
    15.     if(last == '-') ans = -ans;
    16.     return ans;
    17. }
    18. inline void write(ll x)
    19. {
    20.     if(x < 0) x = -x, putchar('-');
    21.     if(x >= 10) write(x / 10);
    22.     putchar(x % 10 + '0');
    23. }
    24.  
    25. ll n;
    26.  
    27. In ll mul(ll a, ll b, ll mod) 
    28. {
    29.     ll d = (long double)a / mod * b + 1e-8; 
    30.     ll r = a * b - d * mod;
    31.     return r < 0 ? r + mod : r;
    32. }
    33. In ll quickpow(ll a, ll b, ll mod)
    34. {
    35.     ll ret = 1;
    36.     for(; b; b >>= 1, a = mul(a, a, mod))
    37.         if(b & 1) ret = mul(ret, a, mod);
    38.     return ret;
    39. }
    40.  
    41. In bool test(ll a, ll d, ll n)
    42. {
    43.     ll t = quickpow(a, d, n);
    44.     if(t == 1) return 1;
    45.     while(d != n - 1 && t != n - 1 && t != 1) t = mul(t, t, n), d <<= 1;
    46.     return t == n - 1;                
    47. }
    48. int a[] = {2, 3, 5, 7, 11};
    49. In bool miller_rabin(ll n)
    50. {
    51.     if(n == 1) return 0;
    52.     for(int i = 0; i < 5; ++i)     
    53.     {
    54.         if(n == a[i]) return 1;
    55.         if(!(n % a[i])) return 0;
    56.     }
    57.     ll d = n - 1;
    58.     while(!(d & 1)) d >>= 1;
    59.     for(int i = 1; i <= 5; ++i)   
    60.     {
    61.         ll a = rand() % (n - 2) + 2;
    62.         if(!test(a, d, n)) return 0;
    63.     }
    64.     return 1;
    65. }
    66.  
    67. In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
    68. In ll f(ll x, ll a, ll mod) {return (mul(x, x, mod) + a) % mod;}
    69. const int M = (1 << 7) - 1;     
    70. ll pollard_rho(ll n)                   
    71. {
    72.     for(int i = 0; i < 5; ++i) if(n % a[i] == 0) return a[i];
    73.     ll x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;
    74.     for(int k = 2;; k <<= 1, y = x) 
    75.     {
    76.         ll q = 1;
    77.         for(int i = 1; i <= k; ++i) 
    78.         {
    79.             x = f(x, a, n);
    80.             q = mul(q, abs(x - y), n);
    81.             if(!(i & M))   
    82.             {
    83.                 t = gcd(q, n);
    84.                 if(t > 1) break;    
    85.             }
    86.         }
    87.         if(t > 1 || (t = gcd(q, n)) > 1) break;  
    88.     }
    89.     return t;
    90. }
    91. In void find(ll x)
    92. {
    93.     if(x == 1 ) return;
    94.     if(miller_rabin(x)) {ans[x]++;return;}
    95.     ll p = x;
    96.     while(p == x) p = pollard_rho(x);
    97.     while(x % p == 0) x/=p;
    98.     find(p); find(x);
    99. }
    100. const ll mod=998244353;
    101. ll modpow(ll x,ll n){
    102. 	x%=mod;
    103. 	if(!x)return 0;
    104. 	ll res=1;
    105. 	for(;n;n>>=1,x=1ll*x*x%mod){
    106. 		if(n&1)res=1ll*res*x%mod;
    107. 	}
    108. 	return res;
    109. }
    110. ll cal(ll p,ll e){
    111. 	//printf("p:%lld e:%lld\n",p,e);
    112. 	return (modpow(p,e+1)+modpow(p,e)-1+mod)%mod*modpow(p,2*e-1)%mod;
    113. }
    114. int main()
    115. {
    116.     srand(time(0));
    117.     int T = read();
    118.     while(T--)
    119.     {
    120.     	ans.clear();
    121.         n = read();
    122.         ll m=n-1;
    123.         find(m);
    124.         ll phi=m%mod,res=1;
    125.         for(auto &v:ans){
    126.         	ll p=v.first,e=0;
    127.         	while(m%p==0)m/=p,e++;
    128.         	res=res*cal(p,e)%mod;
    129.         }
    130.         res=(res+phi*phi%mod)%mod;
    131.         printf("%lld\n",res);
    132.     }
    133.     return 0;
    134. }

    代码2（SSerxhs代码）

    1. #include
    2. using namespace std;
    3. #define In inline
    4. typedef long long ll;
    5. typedef double db;
    6. typedef pairint> P;
    7. #define rep(i,a,b) for(int i=(a);i<=(b);++i)
    8. const int INF = 0x3f3f3f3f;
    9. const db eps = 1e-8;
    10. mapint>ans;
    11. vector
      ans2;
    12. inline ll read()
    13. {
    14.     ll ans = 0;
    15.     char ch = getchar(), last = ' ';
    16.     while(!isdigit(ch)) {last = ch; ch = getchar();}
    17.     while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}
    18.     if(last == '-') ans = -ans;
    19.     return ans;
    20. }
    21. inline void write(ll x)
    22. {
    23.     if(x < 0) x = -x, putchar('-');
    24.     if(x >= 10) write(x / 10);
    25.     putchar(x % 10 + '0');
    26. }
    27.  
    28. ll n;
    29.  
    30. In ll mul(ll a, ll b, ll mod) 
    31. {
    32.     ll d = (long double)a / mod * b + 1e-8; 
    33.     ll r = a * b - d * mod;
    34.     return r < 0 ? r + mod : r;
    35. }
    36. In ll quickpow(ll a, ll b, ll mod)
    37. {
    38.     ll ret = 1;
    39.     for(; b; b >>= 1, a = mul(a, a, mod))
    40.         if(b & 1) ret = mul(ret, a, mod);
    41.     return ret;
    42. }
    43.  
    44. In bool test(ll a, ll d, ll n)
    45. {
    46.     ll t = quickpow(a, d, n);
    47.     if(t == 1) return 1;
    48.     while(d != n - 1 && t != n - 1 && t != 1) t = mul(t, t, n), d <<= 1;
    49.     return t == n - 1;                
    50. }
    51. int a[] = {2, 3, 5, 7, 11};
    52. In bool miller_rabin(ll n)
    53. {
    54.     if(n == 1) return 0;
    55.     for(int i = 0; i < 5; ++i)     
    56.     {
    57.         if(n == a[i]) return 1;
    58.         if(!(n % a[i])) return 0;
    59.     }
    60.     ll d = n - 1;
    61.     while(!(d & 1)) d >>= 1;
    62.     for(int i = 1; i <= 5; ++i)   
    63.     {
    64.         ll a = rand() % (n - 2) + 2;
    65.         if(!test(a, d, n)) return 0;
    66.     }
    67.     return 1;
    68. }
    69.  
    70. In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
    71. In ll f(ll x, ll a, ll mod) {return (mul(x, x, mod) + a) % mod;}
    72. const int M = (1 << 7) - 1;     
    73. ll pollard_rho(ll n)                   
    74. {
    75.     for(int i = 0; i < 5; ++i) if(n % a[i] == 0) return a[i];
    76.     ll x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;
    77.     for(int k = 2;; k <<= 1, y = x) 
    78.     {
    79.         ll q = 1;
    80.         for(int i = 1; i <= k; ++i) 
    81.         {
    82.             x = f(x, a, n);
    83.             q = mul(q, abs(x - y), n);
    84.             if(!(i & M))   
    85.             {
    86.                 t = gcd(q, n);
    87.                 if(t > 1) break;    
    88.             }
    89.         }
    90.         if(t > 1 || (t = gcd(q, n)) > 1) break;  
    91.     }
    92.     return t;
    93. }
    94. In void find(ll x)
    95. {
    96.     if(x == 1 ) return;
    97.     if(miller_rabin(x)) {ans[x]++;return;}
    98.     ll p = x;
    99.     while(p == x) p = pollard_rho(x);
    100.     while(x % p == 0) x/=p;
    101.     find(p); find(x);
    102. }
    103. const ll mod=998244353;
    104. ll modpow(ll x,ll n){
    105. 	x%=mod;
    106. 	if(!x)return 0;
    107. 	ll res=1;
    108. 	for(;n;n>>=1,x=1ll*x*x%mod){
    109. 		if(n&1)res=1ll*res*x%mod;
    110. 	}
    111. 	return res;
    112. }
    113. ll cal(ll p,ll e){
    114. 	//printf("p:%lld e:%lld\n",p,e);
    115. 	return (modpow(p,e+1)+modpow(p,e)-1+mod)%mod*modpow(p,2*e-1)%mod;
    116. }
    117. ll sol(){
    118. 	ll ta=1;//tt=1;
    119. 	for(auto &x:ans2){
    120. 		ll p=x.first,ans=0;
    121. 		int k=x.second;
    122. 		p%=mod;
    123. 		vector f(k+1),pw(k+1),num(k+1);
    124. 		pw[0]=1;
    125. 		rep(i,1,k)pw[i]=pw[i-1]*p%mod;
    126. 		rep(i,0,k-1)num[i]=(pw[k-i]+mod-pw[k-i-1])%mod;
    127. 		num[k]=1;
    128. 		rep(i,0,k){
    129. 			ll ni=num[i];
    130. 			rep(j,0,k){
    131. 				ll nj=num[j];
    132. 				f[min(k,i+j)]=(f[min(k,i+j)]+ni*nj%mod)%mod;
    133. 			}
    134. 		}
    135. 		rep(i,0,k){
    136. 			ll tmp=f[i]*modpow(num[i],mod-2)%mod;
    137. 			ans=(ans+tmp*tmp%mod*num[i]%mod)%mod;
    138. 		}
    139. 		ta=ta*ans%mod;
    140. 	}
    141. 	return ta;
    142. }
    143. int main()
    144. {
    145.     srand(time(0));
    146.     int T = read();
    147.     while(T--)
    148.     {
    149.     	ans.clear();
    150.         ans2.clear();
    151.         n = read();
    152.         ll m=n-1;
    153.         find(m);
    154.         //ll phi=m%mod,res=1;
    155.         for(auto &v:ans){
    156.         	ll p=v.first,e=0;
    157.         	while(m%p==0)m/=p,e++;
    158.         	ans2.push_back(P(p,e));
    159.         	//res=res*cal(p,e)%mod;
    160.         }
    161.         m=(n-1)%mod;
    162.         ll res=sol();
    163.         res=(res+m*m%mod)%mod;
    164.         printf("%lld\n",res);
    165.         //res=(res+phi*phi%mod)%mod;
    166.         //printf("%lld\n",res);
    167.     }
    168.     return 0;
    169. }

  • 相关阅读:
    LVGL---基础对象的事件(events)
    Netty原理与基础
    python 装饰器
    【树莓派不吃灰】使用frp内网穿透，实现远程访问树莓派
    Nginx篇---第三篇
    【Qt】界面优化
    使用Postman拦截浏览器请求
    java常见题
    MasterAlign相机参数设置-曝光时间调节
    我这个代码可以通过深度优先搜索实现逆拓扑排序时检测出有回路的存在吗
  • 原文地址：https://blog.csdn.net/Code92007/article/details/133254179