首页 > 其他分享 >NTT、原根

NTT、原根

时间:2023-05-14 21:11:29浏览次数:27  
标签:2p 原根 质数 NTT delta mod

原根

定义

  • 阶:\(\delta_{mod}a\) 为最小的 \(x\) 满足 \(a^x\equiv1\pmod {mod}\)。
  • 原根:若 \(x,mod\) 满足 \(\delta_{mod}x = \varphi (mod)\) 时,\(x\) 是 \(mod\) 的一个原根。

性质

  • \(mod\) 有原根的充要条件:\(mod = 2,4,p^k,2p^k\),\(p\) 是奇质数

### 求一个数的所有原根

标签:2p,原根,质数,NTT,delta,mod
From: https://www.cnblogs.com/cjoierzdc/p/17400202.html

相关文章

  • python3 xml.etree.ElementTree.ElementTree
    1、介绍对应整个xml结构。2、初始化classElementTree:def__init__(self,element=None,file=None):self._root=element#firstnodeiffile:self.parse(file)element,ElementTree.Element类型,即设置一个节点对象作为根节点file,str......
  • NTT笔记
    NTT笔记前言:这个算法是与FFT类似的,本片不会再从头讲起,建议先去补补课《FFT笔记》。本文只会讲一下互相关联的地方与一些不同的地方。建议:在电脑前放好演算纸和笔。注:本篇文章是我这个小蒟弱写的,真正的dalao请看个玩笑便好,不必争论对错(但是欢迎指出文章存在的小错误)。NT......
  • FFT&NTT学习笔记
    概念多项式乘法时,我们发现暴力乘十分缓慢,但是点值乘十分快速。考虑求\(A\)和\(B\)的卷积。一个\(n\)次多项式可以被\(n+1\)个点确定。设多项式\(A(x)\)的系数为\((a_0,a_1,\cdots,a_n)\)对其奇偶分类得\(A(x)=\sum\limitsa_{2i}*x^{2i}+\suma_{2i+1}*x^{2i+1}\)......
  • $.ajax 中的contentType
    $.ajaxcontentType和dataType,contentType主要设置你发送给服务器的格式,dataType设置你收到服务器数据的格式。在http请求中,get和post是最常用的。在jquery的ajax中,contentType都是默认的值:application/x-www-form-urlencoded,这种格式的特点就是,name/value成为一......
  • vicky自己都看不懂的FFT&NTT&FWT(目前只完成FFT部分
    打个广告QwQ对应的FFT洛谷blog链接对应的csdn博客链接个人觉得洛谷的观感最好。不忘历史八百年前学了\(\text{FFT}\),因vicky过于垃圾,遂放弃。七百年前重拾\(\text{FFT}\),勉强搞懂了它的递归写法,因vicky再一次懒癌附体,遂连板题都没写就弃疗了。历史的今天(是今天才怪),vick......
  • WordCountTopology 执行日志分析
    1,代码packagestorm.starter;importbacktype.storm.Config;importbacktype.storm.LocalCluster;importbacktype.storm.StormSubmitter;importbacktype.storm.task.ShellBolt;importbacktype.storm.topology.BasicOutputCollector;importbacktype.storm.topology.I......
  • SegmentTree
    线段树SegmentTree功能:计算子数组累加和支持区间修改,新增publicclassSegmentTree{intMAX;int[]arr;int[]sum;int[]lazy;int[]change;boolean[]update;publicSegmentTree(int[]origin){this.MAX=origin.length+......
  • 【学习笔记】原根
    原根是\(NTT\)的前置,想学\(NTT\)就得先学求原根。由于作者个人时间原因,原根直接讲结论。 只有\(2,4,p^c,2\timesp^c\)有原根,其中\(c\)为奇质数。\(n\)的原根大概在\(n^{0.25}\)左右,且分布密集。检测\(p\)是否是原根,要看对于所有的\(\phi(n)\)的质数\(k\),是否......
  • jquery ajax contentType为application/json及设置请求头header
    1.找了好久发现contentType一般为默认的application/x-www-form-urlencoded,这次post请求后台限定了为application/json2.当设置contentType为application/json还是出错时,把data也要转换一下$.ajax({method:"POST",url:"",contentType:'application/json',......
  • 微信小程序中target和currentTarget的区别
    微信小程序中target和currentTarget的区别<viewclass="outer-view"bindtap="outerHandler">​<buttontype="primary">按钮</button></view>点击内部按钮时,点击事件会通过冒泡的方式,向外扩散,触发view的tap事件,此时target指向触发事件源头,就是button,而c......