当前位置: 首页 > news >正文

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)

#include<bits/stdc++.h>
using namespace std;
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
map<ll,ll>ans;
inline ll read()
{ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) {last = ch; ch = getchar();}while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}if(last == '-') ans = -ans;return ans;
}
inline void write(ll x)
{if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0');
}ll n;In ll mul(ll a, ll b, ll mod) 
{ll d = (long double)a / mod * b + 1e-8; ll r = a * b - d * mod;return r < 0 ? r + mod : r;
}
In ll quickpow(ll a, ll b, ll mod)
{ll ret = 1;for(; b; b >>= 1, a = mul(a, a, mod))if(b & 1) ret = mul(ret, a, mod);return ret;
}In bool test(ll a, ll d, ll n)
{ll t = quickpow(a, d, n);if(t == 1) return 1;while(d != n - 1 && t != n - 1 && t != 1) t = mul(t, t, n), d <<= 1;return t == n - 1;                
}
int a[] = {2, 3, 5, 7, 11};
In bool miller_rabin(ll n)
{if(n == 1) return 0;for(int i = 0; i < 5; ++i)     {if(n == a[i]) return 1;if(!(n % a[i])) return 0;}ll d = n - 1;while(!(d & 1)) d >>= 1;for(int i = 1; i <= 5; ++i)   {ll a = rand() % (n - 2) + 2;if(!test(a, d, n)) return 0;}return 1;
}In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
In ll f(ll x, ll a, ll mod) {return (mul(x, x, mod) + a) % mod;}
const int M = (1 << 7) - 1;     
ll pollard_rho(ll n)                   
{for(int i = 0; i < 5; ++i) if(n % a[i] == 0) return a[i];ll x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;for(int k = 2;; k <<= 1, y = x) {ll q = 1;for(int i = 1; i <= k; ++i) {x = f(x, a, n);q = mul(q, abs(x - y), n);if(!(i & M))   {t = gcd(q, n);if(t > 1) break;    }}if(t > 1 || (t = gcd(q, n)) > 1) break;  }return t;
}
In void find(ll x)
{if(x == 1 ) return;if(miller_rabin(x)) {ans[x]++;return;}ll p = x;while(p == x) p = pollard_rho(x);while(x % p == 0) x/=p;find(p); find(x);
}
const ll mod=998244353;
ll modpow(ll x,ll n){x%=mod;if(!x)return 0;ll res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
ll cal(ll p,ll e){//printf("p:%lld e:%lld\n",p,e);return (modpow(p,e+1)+modpow(p,e)-1+mod)%mod*modpow(p,2*e-1)%mod;
}
int main()
{srand(time(0));int T = read();while(T--){ans.clear();n = read();ll m=n-1;find(m);ll phi=m%mod,res=1;for(auto &v:ans){ll p=v.first,e=0;while(m%p==0)m/=p,e++;res=res*cal(p,e)%mod;}res=(res+phi*phi%mod)%mod;printf("%lld\n",res);}return 0;
}

代码2(SSerxhs代码)

#include<bits/stdc++.h>
using namespace std;
#define In inline
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
map<ll,int>ans;
vector<P>ans2;
inline ll read()
{ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) {last = ch; ch = getchar();}while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}if(last == '-') ans = -ans;return ans;
}
inline void write(ll x)
{if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0');
}ll n;In ll mul(ll a, ll b, ll mod) 
{ll d = (long double)a / mod * b + 1e-8; ll r = a * b - d * mod;return r < 0 ? r + mod : r;
}
In ll quickpow(ll a, ll b, ll mod)
{ll ret = 1;for(; b; b >>= 1, a = mul(a, a, mod))if(b & 1) ret = mul(ret, a, mod);return ret;
}In bool test(ll a, ll d, ll n)
{ll t = quickpow(a, d, n);if(t == 1) return 1;while(d != n - 1 && t != n - 1 && t != 1) t = mul(t, t, n), d <<= 1;return t == n - 1;                
}
int a[] = {2, 3, 5, 7, 11};
In bool miller_rabin(ll n)
{if(n == 1) return 0;for(int i = 0; i < 5; ++i)     {if(n == a[i]) return 1;if(!(n % a[i])) return 0;}ll d = n - 1;while(!(d & 1)) d >>= 1;for(int i = 1; i <= 5; ++i)   {ll a = rand() % (n - 2) + 2;if(!test(a, d, n)) return 0;}return 1;
}In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
In ll f(ll x, ll a, ll mod) {return (mul(x, x, mod) + a) % mod;}
const int M = (1 << 7) - 1;     
ll pollard_rho(ll n)                   
{for(int i = 0; i < 5; ++i) if(n % a[i] == 0) return a[i];ll x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;for(int k = 2;; k <<= 1, y = x) {ll q = 1;for(int i = 1; i <= k; ++i) {x = f(x, a, n);q = mul(q, abs(x - y), n);if(!(i & M))   {t = gcd(q, n);if(t > 1) break;    }}if(t > 1 || (t = gcd(q, n)) > 1) break;  }return t;
}
In void find(ll x)
{if(x == 1 ) return;if(miller_rabin(x)) {ans[x]++;return;}ll p = x;while(p == x) p = pollard_rho(x);while(x % p == 0) x/=p;find(p); find(x);
}
const ll mod=998244353;
ll modpow(ll x,ll n){x%=mod;if(!x)return 0;ll res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
ll cal(ll p,ll e){//printf("p:%lld e:%lld\n",p,e);return (modpow(p,e+1)+modpow(p,e)-1+mod)%mod*modpow(p,2*e-1)%mod;
}
ll sol(){ll ta=1;//tt=1;for(auto &x:ans2){ll p=x.first,ans=0;int k=x.second;p%=mod;vector<ll> f(k+1),pw(k+1),num(k+1);pw[0]=1;rep(i,1,k)pw[i]=pw[i-1]*p%mod;rep(i,0,k-1)num[i]=(pw[k-i]+mod-pw[k-i-1])%mod;num[k]=1;rep(i,0,k){ll ni=num[i];rep(j,0,k){ll nj=num[j];f[min(k,i+j)]=(f[min(k,i+j)]+ni*nj%mod)%mod;}}rep(i,0,k){ll tmp=f[i]*modpow(num[i],mod-2)%mod;ans=(ans+tmp*tmp%mod*num[i]%mod)%mod;}ta=ta*ans%mod;}return ta;
}
int main()
{srand(time(0));int T = read();while(T--){ans.clear();ans2.clear();n = read();ll m=n-1;find(m);//ll phi=m%mod,res=1;for(auto &v:ans){ll p=v.first,e=0;while(m%p==0)m/=p,e++;ans2.push_back(P(p,e));//res=res*cal(p,e)%mod;}m=(n-1)%mod;ll res=sol();res=(res+m*m%mod)%mod;printf("%lld\n",res);//res=(res+phi*phi%mod)%mod;//printf("%lld\n",res);}return 0;
}

相关文章:

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

题目 T(T<10)组样例&#xff0c;每次给出一个n(2<n<1e18)&#xff0c; 询问多少对&#xff0c;满足 答案对998244353取模&#xff0c;保证n-1不是998244353倍数 思路来源 OEIS、SSerxhs、官方题解 2023 ICPC 网络赛 第一场简要题解 - 知乎 题解 官方题解还没有…...

<十三>objectARX开发:模拟实现CAD的移动Move命令

一、目的 实现类似于CAD的移动命令,选择对象,移动到指定位置,移动过程中对象跟随鼠标移动。效果如下: 二、关键步骤 选择对象,打开实体判断类型:acedEntSel()、acdbOpenObject()、isKindOf()。指定基点:acedGetPoint()。移动模型,追踪光标移动对象实体:acedGrRead()…...

Autosar基础:模式管理-EcuM

ECUM目录 前言一、ECUM状态机二、Fixed和Flexible模式的区别与联系三、状态详解3.1.Startup3.2.UP3.3.RUN3.4.Sleep3.5.Shutdown三、EcuM唤醒源3.1 CAN Trcv唤醒3.2 唤醒后操作前言 根据Autosar对于模式管理的需求定义,模式管理有以下模块: ①ECU State Manager(EcuM):管理…...

代码随想录Day42 | 01背包问题| 416. 分割等和子集

01背包问题&#xff08;Acwing&#xff09; 有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入…...

UML六大关系总结

UML六大关系有&#xff1a;继承、关系、聚合、组合、实现、依赖。分为通过图和代码总结这些关系。 1、继承 继承&#xff08;Inheritance&#xff09;&#xff1a;表示类之间的继承关系&#xff0c;子类继承父类的属性和方法&#xff0c;并可以添加自己的扩展。 继承&#x…...

ElementUI基本介绍及登录注册案例演示

目录 前言 一.简介 二.优缺点 三.Element完成登录注册 1. 环境配置及前端演示 1.1 安装Element-UI模块 1.2 安装axios和qs(发送get请求和post请求) 1.3 导入依赖 2 页面布局 2.1组件与界面 3.方法实现功能数据交互 3.1 通过方法进行页面跳转 3.2 axios发送get请求 …...

Python爬虫-某网酒店评论数据

前言 本文是该专栏的第6篇,后面会持续分享python爬虫案例干货,记得关注。 本文以某网的酒店数据为例,采集对应酒店的评论数据。具体思路和方法跟着笔者直接往下看正文详细内容。(附带完整代码) 注意:本文的案例“数据集”,选用的是本专栏上一篇“Python爬虫-某网酒店数…...

C# Onnx Yolov8 Detect 水果识别

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System…...

测试网页调用本地可执行程序(续1:解析参数中的中文编码)

学习测试网页调用本地可执行程序还遗留一个问题&#xff0c;即网页中调用带中文参数的命令时&#xff0c;本地可执行程序接收到的参数字符串里的中文都转换成了编码模式&#xff0c;看起来如下所示&#xff1a; <a href TestPageCall:-a你好>启动测试程序</a><…...

C++入门知识

Hello&#xff0c;今天我们分享一些关于C入门的知识&#xff0c;看完至少让你为后面的类和对象有一定的基础&#xff0c;所以在讲类和对象的时候&#xff0c;我们需要来了解一些关于C入门的知识。 什么是C C语言是结构化和模块化的语言&#xff0c;适合处理较小规模的程序。对…...

spring和springmvc常用注解

1.Spring常用注解&#xff1a; 1&#xff09;Repository将DAO类声明为Bean 2&#xff09;Service用于修饰service层的组件 3&#xff09;Controller通常作用在控制层&#xff0c;将在Spring MVC中使用 4&#xff09;Component是一个泛化的概念&#xff0c;仅仅表示spring中的一…...

【Java】Java生成PDF工具类

Java生成PDF工具类 一、介绍 Java生成PDF工具类是一个非常实用的工具类&#xff0c;可以帮助我们以程序化的方式生成PDF文件。通过该工具类&#xff0c;我们可以向PDF文件中添加文字、图片、表格等多种内容&#xff0c;并且可以进行格式化和样式设置。Java生成PDF工具类常用于…...

STL map,插入和查找的一些注意事项

01、前言&#xff08;废话&#xff09; C 的 std::map 容器中插入键值对主要有myMap(std::make_pair(key value)) &#xff0c;它们的区别你了解吗&#xff1f; auto it myMap,find(key) 和 auto value myMap[key] 都可以用于在 C 的 std::map 容器中查找键对应的值&#xff…...

基于springboot+vue的客户关系管理系统(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...

【Java 基础篇】Java Stream 流详解

Java Stream&#xff08;流&#xff09;是Java 8引入的一个强大的新特性&#xff0c;用于处理集合数据。它提供了一种更简洁、更灵活的方式来操作数据&#xff0c;可以大大提高代码的可读性和可维护性。本文将详细介绍Java Stream流的概念、用法和一些常见操作。 什么是Stream…...

题解:ABC321A - 321-like Checker

题解&#xff1a;ABC321A - 321-like Checker 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;C。 思维难度&#xff1a;C。 调码难度&#xff1a;C。 综合评价&#xff1a;见洛谷链接。 算法 模拟。 思路 输入n后从后往前依次抽…...

Zig实现Hello World

1. 什么是zig 先列出一段官方的介绍: Zig is a general-purpose programming language and toolchain for maintaining robust, optimal, and reusable software. 大概意思就是说&#xff1a; Zig是一种通用编程语言和工具链&#xff0c;用于维护健壮、最佳和可重用的软件。 官…...

Vue3+element-plus切换标签页时数据保留问题

记录一次切换标签页缓存失效问题&#xff0c;注册路由时name不一致可能会导致缓存失效...

前端教程-TypeScript

官网 TypeScript官网 TypeScript中文官网 视频教程 尚硅谷TypeScript教程&#xff08;李立超老师TS新课&#xff09;...

代码随想录算法训练营 动态规划part06

一、完全背包 卡哥的总结&#xff0c;还挺全代码随想录 (programmercarl.com) 二、零钱兑换 II 518. 零钱兑换 II - 力扣&#xff08;LeetCode&#xff09; 被选物品之间不需要满足特定关系&#xff0c;只需要选择物品&#xff0c;以达到「全局最优」或者「特定状态」即可。 …...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...