当前位置: 首页 > 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;以达到「全局最优」或者「特定状态」即可。 …...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...