凉州区新农村建设网站,网站搜索不到了,有哪些网站做的比较好看,网站网站制作多少钱感觉这一块讲的有点太少了#xff0c;只有辗转相除法#xff0c;拓展欧几里得定理#xff0c;素数筛#xff0c;快速幂和逆元五个内容。数论的内容远远不止这些。不过一个视频也讲不了太多东西#xff0c;讲的还是数学#xff0c;也是没有办法。一边看题一边说吧。
辗转…感觉这一块讲的有点太少了只有辗转相除法拓展欧几里得定理素数筛快速幂和逆元五个内容。数论的内容远远不止这些。不过一个视频也讲不了太多东西讲的还是数学也是没有办法。一边看题一边说吧。
辗转相除法
辗转相除法又叫欧几里得算法用来求解两个数的最大公因数GCDGreatest Common Divisor。内容是 g c d ( a , b ) g c d ( b , a % b ) gcd(a,b)gcd(b,a\%b) gcd(a,b)gcd(b,a%b)。中国有一个类似的算法叫做更相减损术内容是 g c d ( a , b ) g c d ( a , a − b ) g c d ( b , a − b ) gcd(a,b)gcd(a,a-b)gcd(b,a-b) gcd(a,b)gcd(a,a−b)gcd(b,a−b) 其实内容上和欧几里得算法是一个东西。
证明 g c d ( a , b ) g c d ( b , a % b ) gcd(a,b)gcd(b,a\%b) gcd(a,b)gcd(b,a%b) 不妨假设 a b ab ab。设 d g c d ( a , b ) dgcd(a,b) dgcd(a,b) 那么 a k 1 ∗ d , b k 2 ∗ d ak_1*d,bk_2*d ak1∗d,bk2∗d 则有 a % b a − m ∗ b k 1 ∗ d − m ∗ k 2 ∗ d ( k 1 − m ∗ k 2 ) ∗ d a\%ba-m*bk_1*d-m*k_2*d(k_1-m*k_2)*d a%ba−m∗bk1∗d−m∗k2∗d(k1−m∗k2)∗d余数仍然是最大公因数 d d d 的倍数。 还有种证明方法是这样的 a q ∗ b r aq*br aq∗br其中 0 ≤ r b 0\le r\lt b 0≤rb那么 a % b r a\%br a%br。因为 a , b a,b a,b 的最大公因数 d d d 可以整除 a , b a,b a,b即 d ∣ a d|a d∣a 且 d ∣ b d|b d∣b 所以 d ∣ ( q ∗ b ) d|(q*b) d∣(q∗b)所以 d ∣ ( r a − q ∗ b ) d|(ra-q*b) d∣(ra−q∗b)也就是说明余数 r r r 是 d d d 的倍数。
而 ( a , b ) → ( b , a % b ) (a,b)\rightarrow(b,a\%b) (a,b)→(b,a%b) 是不断减小的因此这样算下去的话最终就会得到 a % b 0 a\%b0 a%b0此时的 a a a 就是最大公因数。这个辗转相除的过程最多不会超过 l o g log log 次因此求解 g c d gcd gcd 的时间复杂度是 O ( l o g n ) O(logn) O(logn)
代码片段如下 这里不需要判断ab谁大谁小并交换因为再调用一次 gcd(b,a%b) 就实现了交换。
int gcd(int a,int b){return (b)?gcd(b,a%b):a;
}更神秘的写法 其实就是每次先对a模上b然后交换abb^a^b^实现的其实就是交换功能。
int gcd(int,a,int b){while(b)b^a^b^a%b;return a;
}拓展欧几里得定理
也就是exgcdExtended gcd。它主要是用来求解一次线性同余方程。也就是形如 a ∗ x ≡ c ( m o d p ) a*x\equiv c\pmod p a∗x≡c(modp) 求 x x x 的通解问题。这一篇讲的比较好
对这种问题我们可以稍加转化得到 a ∗ x p ∗ y c a*xp*yc a∗xp∗yc 的等式换种写法就是 a ∗ x b ∗ y c a*xb*yc a∗xb∗yc变成了二元一次方程求通解问题。在解决这个问题之前我们可以算出 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 问题的通解然后通过这个算式可以得到我们所求算式的通解。那么怎么求 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 的通解呢。
贝祖定理 B e ˊ z o u t B\ezout Beˊzout 定理
内容是 对任意整数 a , b a,b a,b存在一对整数 x , y x,y x,y满足方程 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 。
证明使用归纳法。当 b 0 b0 b0 时 x 1 , y 0 x1,y0 x1,y0 显然是方程的一组解 g c d ( a , 0 ) a gcd(a,0)a gcd(a,0)a。
当 b 0 b0 b0设我们知道方程 b ∗ x ( a % b ) ∗ y g c d ( b , a % b ) g c d ( a , b ) b*x(a\%b)*ygcd(b,a\%b)gcd(a,b) b∗x(a%b)∗ygcd(b,a%b)gcd(a,b) 的解求 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 的解。 b ∗ x ( a % b ) ∗ y g c d ( b , a % b ) b*x(a\%b)*ygcd(b,a\%b) b∗x(a%b)∗ygcd(b,a%b) b ∗ x ( a − b ∗ ⌊ a b ⌋ ) ∗ y g c d ( a , b ) b*x(a-b*\left\lfloor\frac ab\right\rfloor)*ygcd(a,b) b∗x(a−b∗⌊ba⌋)∗ygcd(a,b) a ∗ y b ∗ x − b ∗ ⌊ a b ⌋ ∗ y g c d ( a , b ) a*yb*x-b*\left\lfloor\frac ab\right\rfloor*ygcd(a,b) a∗yb∗x−b∗⌊ba⌋∗ygcd(a,b) a ∗ y b ∗ ( x − ⌊ a b ⌋ ∗ y ) g c d ( a , b ) a*yb*(x-\left\lfloor\frac ab\right\rfloor*y)gcd(a,b) a∗yb∗(x−⌊ba⌋∗y)gcd(a,b)
设 b ∗ x ( a % b ) ∗ y g c d ( b , a % b ) b*x(a\%b)*ygcd(b,a\%b) b∗x(a%b)∗ygcd(b,a%b) 一组特解是 ( x 0 , y 0 ) (x_0,y_0) (x0,y0) 可以发现 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 一组可行解就是 x y 0 , y x 0 − ⌊ a b ⌋ ∗ y 0 xy_0,yx_0-\left\lfloor\frac ab\right\rfloor*y_0 xy0,yx0−⌊ba⌋∗y0。我们用辗转相除法向下走到尽头从最下面的 a ∗ 1 b ∗ 0 g c d ( a , 0 ) a*1b*0gcd(a,0) a∗1b∗0gcd(a,0) 一步一步向上推理就可以得到原本式子的一组特解。
得到特解后会想得到 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 的通解这个好说 a ∗ x a*x a∗x 多一个 a ∗ b g c d ( a , b ) \dfrac{a*b}{gcd(a,b)} gcd(a,b)a∗b那么 b ∗ y b*y b∗y 就少一个 a ∗ b g c d ( a , b ) \dfrac{a*b}{gcd(a,b)} gcd(a,b)a∗b 就行了。也就是说 x x x 每加一个 b g c d ( a , b ) \dfrac{b}{gcd(a,b)} gcd(a,b)b y y y 就减少一个 a g c d ( a , b ) \dfrac{a}{gcd(a,b)} gcd(a,b)a可以维持等式不变。写成式子就是通解 x ‾ x k ∗ b g c d ( a , b ) , y ‾ y − k ∗ a g c d ( a , b ) \overline xxk*\dfrac{b}{gcd(a,b)},\overline yy-k*\dfrac{a}{gcd(a,b)} xxk∗gcd(a,b)b,yy−k∗gcd(a,b)a。令 t 1 b g c d ( a , b ) t1\dfrac{b}{gcd(a,b)} t1gcd(a,b)b那么就是 x ‾ x k ∗ t 1 \overline xxk*t1 xxk∗t1这相当于通解模 t 1 t1 t1 同余特解即 x ‾ ≡ x ( m o d t 1 ) \overline x\equiv x\pmod{t1} x≡x(modt1)因此求 x x x 的最小非负整数解就是 ( x % t 1 t 1 ) % t 1 (x\%t1t1)\%t1 (x%t1t1)%t1同理 y y y 的通解。
代码片段如下
int exgcd(int a,int b,int x,int y){if(!b){x1;y0;return a;}int dexgcd(b,a%b,x,y);int zx;xy;yz-(a/b)*y;return d;
}压行
int exgcd(int a,int b,int x,int y){if(!b){x1;y0;return a;}int dexgcd(b,a%b,y,x);//这里相当于交换了xy的值y-a/b*x;return d;
}另外提一嘴对任意一个方程 a ∗ x b ∗ y d g c d ( a , b ) a*xb*ydgcd(a,b) a∗xb∗ydgcd(a,b) 等式两边同时除以最大公因数 d d d就得到了 a d ∗ x b d ∗ y 1 \dfrac ad*x\dfrac bd*y1 da∗xdb∗y1 解和上面是一样的。也就是说当 a , b a,b a,b 互质时 a ∗ x b ∗ y 1 a*xb*y1 a∗xb∗y1 一定有解。反之也成立不然你 a , b a,b a,b 都是 d d d 的倍数 x , y x,y x,y 是整数它们乘积的和也一定是 d d d 的倍数但是 1 1 1 不包含任何大于1的因数因此 a , b a,b a,b 不可能同时是任何一个 d d d 的倍数。
拓展欧几里得值域分析
因为在这里面无法取模否则会导致出错所以会担心运算过程中出现超大的数导致溢出。不过安心所有x和y的中间值的绝对值都小于 ∣ m a x { a , b } ∣ |max\{a,b\}| ∣max{a,b}∣。证明还是数学归纳法。详细的证明步骤在上面给出的博客中详细证明了。不多赘述。
裴蜀定理
内容设 a , b a,b a,b 为正整数则关于 a , b a,b a,b 的方程 a ∗ x b ∗ y c a*xb*yc a∗xb∗yc 有整数解当且仅当 c c c 是 g c d ( a , b ) gcd(a,b) gcd(a,b) 的倍数。
也就是说如果 c c c 不能被 g c d ( a , b ) gcd(a,b) gcd(a,b) 整除方程无整数解否则有整数解。不证明了。
我们通过上面的方式得到了 a ∗ x b ∗ y g c d ( a , b ) a*xb*ygcd(a,b) a∗xb∗ygcd(a,b) 一组特解现在要得到 a ∗ x b ∗ y c a*xb*yc a∗xb∗yc 通解。先算特解再找到通解的之间的变化量即可。这个好说假设 c k ∗ d ck*d ck∗d 那么在等式 a ∗ x b ∗ y d g c d ( a , b ) a*xb*ydgcd(a,b) a∗xb∗ydgcd(a,b) 两边同时乘以 k c d k\dfrac cd kdc 就完事了式子就变成了 a ∗ ( c d ⋅ x ) b ∗ ( c d ⋅ y ) c a*(\dfrac cd\cdot x)b*(\dfrac cd\cdot y)c a∗(dc⋅x)b∗(dc⋅y)c。新的特解就是 x c d ⋅ x , y c d ⋅ y x\dfrac cd\cdot x,y\dfrac cd\cdot y xdc⋅x,ydc⋅y。不过由于系数没变所以变化量是不变的还是 t 1 b d , t 2 a d t1\dfrac bd,t2\dfrac ad t1db,t2da。
总结通过拓展欧几里得算法可以算出等式 a ∗ x b ∗ y d g c d ( a , b ) a*xb*ydgcd(a,b) a∗xb∗ydgcd(a,b) 一组特解 x 0 , y 0 x_0,y_0 x0,y0那么等式 a ∗ x b ∗ y c a*xb*yc a∗xb∗yc 一组特解是 x c / d ∗ x 0 , y 0 c / d ∗ y 0 xc/d*x_0,y_0c/d*y_0 xc/d∗x0,y0c/d∗y0通解 x ‾ \overline x x 的变化量是 t 1 b / d t1b/d t1b/d通解 y ‾ \overline y y 的变化量是 t 2 a / d t2a/d t2a/d。等式 a ∗ x b ∗ y c a*xb*yc a∗xb∗yc 的通解为 x ‾ x k ∗ t 1 , y ‾ y − k ∗ t 2 \overline xxk*t1,\overline yy-k*t2 xxk∗t1,yy−k∗t2 素数筛
试除法开方暴力
我们想要知道一个数 x x x 是不是素数朴素的想法是枚举 2 ∼ x − 1 2\sim x-1 2∼x−1 暴力地尝试 x x x 能不能被其中一个整除。这样是 O ( n ) O(n) O(n) 的。一个显而易见的性质是如果一个数 x x x 是合数那么它一定存在一个质因数 p p p而且 2 ≤ p ≤ x 2\le p \le \sqrt x 2≤p≤x 。
反证法证明假设合数 x x x 最小质因数为 p p p如果上述性质不满足条件说明 p x p\sqrt x px 因为 x x x 为合数因此 x x x 存在至少一个另一个质因数 q q q根据题设 p p p 是最小的质因数因此 q q qq qq那么有 p ∗ q ≥ p 2 ( x ) 2 x p*q\ge p^2(\sqrt x)^2x p∗q≥p2(x )2x两个因数的乘积大于了这个数矛盾因此 2 ≤ p ≤ x 2\le p \le \sqrt x 2≤p≤x 。
所以我们枚举 2 ∼ ⌊ x ⌋ 2\sim \lfloor\sqrt x\rfloor 2∼⌊x ⌋ 就行了时间复杂度是 O ( n ) O(\sqrt n) O(n )。代码如下
bool isp(int x){if(x1)return false;for(int i2;i*ix;i)if(x%i0)return false;return true;
}埃式筛
我们从 2 2 2 往后看每个数如果这个数是质数直接去标记一下它所有的倍数这样就可以把有这个质因数的合数标记掉。如果一个数是合数那么它一定存在小于它的质因子。如果我们对每个遇到的质因数都这样做那么我们在看到一个合数之前它一定会被标记掉。我们从前往后看到的所有没有标记的数都是素数。所以我们从 1 1 1 到 n n n 走一遍这种操作就可以得到 1 ∼ n 1\sim n 1∼n 中所有的素数。
这种像筛子一样一次一次把合数筛出来的过程就是埃式筛它筛数的次数约有 n / 2 n / 3 n / 5 ⋯ n / p … ( p 是质数 ) ≤ n / 1 n / 2 n / 3 ⋯ n / n n/2n/3n/5\dotsn/p\dots\quad (p是质数)\le n/1n/2n/3\dotsn/n n/2n/3n/5⋯n/p…(p是质数)≤n/1n/2n/3⋯n/n 当 n → ∞ n\rightarrow\infty n→∞ 时 n / 1 n / 2 n / 3 ⋯ n / n n l o g n n/1n/2n/3\dotsn/nnlogn n/1n/2n/3⋯n/nnlogn这东西学名叫调和级数想看证明可以搜因此埃式筛的筛的次数也就是时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)而且是常数很小的 n l o g n nlogn nlogn。代码如下
bool vis[maxn];
void eratosthenes(int n){vis[1]true;for(int i2;in;i){if(!vis[i])for(int j2*i;jn;ji)vis[j]true;}
}欧拉筛
上面发现一个合数可能会被筛去多次有没有办法使得每个数只被筛去一次有。
我们想要一个合数只被它最小的质因数与和它对应的次大的因数最大因数就是它本身筛去。当我们看到一个数的时候枚举目前已经找到的质数质数与我们看到的这个数相乘得到的数就是以枚举的质数为最小质因子的数。当我们枚举的质数已经可以整除我们现在看到的这个数的时候就说明后面的质数不再小于等于我们看到的这个数的最小质因数了就可以退出了。
通过这种想法任何一个合数都一定会被它最小的质因数与和它对应的次大的因数筛去一次。所以时间复杂度是 O ( n ) O(n) O(n) 的。代码如下。
int prime[maxn],cnt;
bool vis[maxn];
void Eular(int n){for(int i2;in;i){if(!vis[i])prime[cnt]i;for(int j1,pprime[1];jcnt i*pn;pprime[j]){vis[i*p]true;if(i%p0)break;}}
}这个筛的过程一定要融会贯通因为它每个筛到的数都一定是这个数最小的质因数来筛这个性质很强所以对这个东西略微修改就可以同时处理很多有用的信息。比如每个数的最小质因数每个数所有的质因数计算欧拉函数莫比乌斯函数等等。 快速幂
普通算 a b a^b ab 的方式就是把 b b b 个 a a a 乘起来时间复杂度是 O ( b ) O(b) O(b) 的。
发现一个东西就是 a ∗ a a 2 , a 2 ∗ a 2 a 4 , a 4 ∗ a 4 a 8 , . . . a*aa^2,a^2*a^2a^4,a^4*a^4a^8,... a∗aa2,a2∗a2a4,a4∗a4a8,... 通过这种方式可以快速算出指数很大的 a a a 的幂然后我们再用预先算出来的这些幂指数去凑出答案的幂指数就行了。
举个例子如果我们要算 a 10 a^{10} a10 那么我们可以先算出来 a 1 , a 2 , a 4 , a 8 a^1,a^2,a^4,a^8 a1,a2,a4,a8然后 a 10 a 2 ∗ a 8 a^{10}a^2*a^8 a10a2∗a8。当指数很大的时候优势就更大了比如 a 1025 a 1024 ∗ a 1 a^{1025}a^{1024}*a^1 a1025a1024∗a1而处理到 a 1024 a^{1024} a1024 只需要十次。
其实这东西有点像二进制我们处理出来的是 a 1 ( 2 ) , a 1 0 ( 2 ) , a 10 0 ( 2 ) , a 100 0 ( 2 ) a^{1_{(2)}},a^{10_{(2)}},a^{100_{(2)}},a^{1000_{(2)}} a1(2),a10(2),a100(2),a1000(2) 相乘其实就是幂指数相加通过幂指数相加得到任何一个我们想要的幂指数。比如 a 10 a 101 0 ( 2 ) a 100 0 ( 2 ) 1 0 ( 2 ) a 100 0 ( 2 ) ∗ a 1 0 ( 2 ) a^{10}a^{1010_{(2)}}a^{1000_{(2)}10_{(2)}}a^{1000_{(2)}}*a^{10_{(2)}} a10a1010(2)a1000(2)10(2)a1000(2)∗a10(2)。想要凑出指数为 b b b二进制位最多 l o g 2 b log_2b log2b 位所以快速幂的时间复杂度为 O ( l o g 2 b ) O(log_2b) O(log2b)
代码如下
ll qpow(ll a,ll b,ll mod){ll basea%mod,ans1;while(b){if(b1){ans*base;ans%mod;}base*base;base%mod;b1;}return ans;
}逆元
这个东西主要是为了解决模意义下不能相除的问题。那么我们怎么才能实现相除呢
假设 b b b 在取模意义下相当于 1 a \dfrac 1a a1 或者说 a − 1 a^{-1} a−1那么有 a ∗ b ≡ 1 ( m o d p ) a*b\equiv1\pmod p a∗b≡1(modp)。
费马小定理
内容若 p p p 是质数且 a a a 不是 p p p 的倍数则有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv1\pmod p ap−1≡1(modp)
它是欧拉定理的一个特例不过在大部分情况下已经够用。这里要特别注意限定条件必须满足。因为 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv1\pmod p ap−1≡1(modp)所以 a p − 2 ∗ a ≡ 1 ( m o d p ) a^{p-2}*a\equiv1\pmod p ap−2∗a≡1(modp)这里 a p − 2 a^{p-2} ap−2 就实现了上面的 b b b 的功能因此 a p − 2 ≡ 1 a ( m o d p ) a^{p-2}\equiv \dfrac 1a\pmod p ap−2≡a1(modp)。
简单来说如果模数是质数 p p p要除以 a a a那么就直接乘以 a p − 2 a^{p-2} ap−2 就可以实现相同的作用了。 A - 最大公约数和最小公倍数问题
思路
如果把 x 0 , y 0 x_0,y_0 x0,y0 质因数分解就得到了 x 0 p 1 c 1 ∗ p 2 c 2 ∗ p 3 c 3 ∗ ⋯ ∗ p i c i , y 0 p 1 t 1 ∗ p 2 t 2 ∗ p 3 t 3 ∗ ⋯ ∗ p j t j x_0p_1^{c_1}*p_2^{c_2}*p_3^{c_3}*\dots*p_i^{c_i},y_0p_1^{t_1}*p_2^{t_2}*p_3^{t_3}*\dots*p_j^{t_j} x0p1c1∗p2c2∗p3c3∗⋯∗pici,y0p1t1∗p2t2∗p3t3∗⋯∗pjtj而且 t i ≥ c i t_i\ge c_i ti≥ci。对 P , Q P,Q P,Q 来说它们肯定都有 x 0 x_0 x0 的质因数部分而从 x 0 x_0 x0 到 y 0 y_0 y0 的这一块质因数部分完全不重合。也就是说从 y 0 x 0 p 1 m 1 ∗ p 2 m 2 ∗ p 3 m 3 ∗ ⋯ ∗ p j m j \frac {y_0} {x_0}p_1^{m_1}*p_2^{m_2}*p_3^{m_3}*\dots*p_j^{m_j} x0y0p1m1∗p2m2∗p3m3∗⋯∗pjmj 取出若干种质因数 p k m k p_k^{m_k} pkmk 分给 P P P剩下的分给 Q Q Q 就是一个可行的解。每种质因数只能分给 P , Q P,Q P,Q 其中一个否则分给 P , Q P,Q P,Q 的部分会出现重合
因为一种质因数要么分给 P P P要么分给 Q Q Q每种质因数有两种选择如果 y 0 x 0 \frac {y_0} {x_0} x0y0 有 x x x 种质因数那么分法也就是答案就有 2 x 2^x 2x 种。
code
#include iostream
#include cstdio
using namespace std;int x,y;int main(){cinxy;if(y%x){cout0;return 0;}xy/x;int cnt0;for(int i2;i*ix;i)if(x%i0){cnt;while(x%i0)x/i;}if(x1)cnt;cout(1llcnt);return 0;
}B - 二元一次不定方程 (exgcd)
思路
求解形如 a ∗ x b ∗ y c a*xb*yc a∗xb∗yc 方程的通解已经在上面详细描述过了这里尝试算出正整数解的个数和 x , y x,y x,y 的最大和最小正整数解。
假设我们已经算到了 x ‾ x k ∗ t 1 , y ‾ y − k ∗ t 2 \overline xxk*t1,\overline yy-k*t2 xxk∗t1,yy−k∗t2。 x , y x,y x,y 的最小正整数解好算先看 x x x 因为是正整数解不是非负整数解不包括0解的值域应该是 [ 1 , t 1 ] [1,t1] [1,t1]所以我们的计算式应该是 x m i n ( ( x − 1 ) % t 1 t 1 ) % t 1 1 x_{min}((x-1)\%t1t1)\%t11 xmin((x−1)%t1t1)%t11同理 y m i n ( ( y − 1 ) % t 2 t 2 ) % t 2 1 y_{min}((y-1)\%t2t2)\%t21 ymin((y−1)%t2t2)%t21。
而 x x x 取到最大正整数解时 y y y 此时应该正好取到最小正整数解因此我们把 y m i n y_{min} ymin 代入算出此时的 x x x 即可。同理 y y y。
正整数解的个数其实就看一个变量就可以了。比如看 x x x 其实就是 x m i n x_{min} xmin 和 x m a x x_{max} xmax 中间差了几个 t 1 t1 t1 。
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;ll T,a,b,c;ll exgcd(ll a,ll b,ll x,ll y){if(!b){x1;y0;return a;}ll dexgcd(b,a%b,x,y);ll zx;xy;yz-(a/b)*y;return d;
}int main(){cinT;while(T--){scanf(%lld%lld%lld,a,b,c);ll x,y,dexgcd(a,b,x,y);if(c%d){printf(-1\n);continue;}xc/d*x;yc/d*y;ll t1b/d,t2a/d;ll xmi((x-1)%t1t1)%t11,ymi((y-1)%t2t2)%t21,xmx,ymx;xmx(c-ymi*b)/a;ymx(c-xmi*a)/b;if(xmx0 || ymx0){printf(%lld %lld\n,xmi,ymi);}else {printf(%lld %lld %lld %lld %lld\n,(xmx-xmi)/t11,xmi,ymi,xmx,ymx);}}return 0;
}C - 质因数分解
思路
枚举所有可能的因数得到的第一个因数对应的另一个因数就是答案。
根据上面提到的性质如果一个数 x x x 是合数那么它一定存在一个质因数 p p p而且 2 ≤ p ≤ x 2\le p \le \sqrt x 2≤p≤x 。我们最多找到 x \sqrt x x 就能找到答案了。
code
#include iostream
#include cstdio
using namespace std;int n;int main(){cinn;for(int i2;i*in;i)if(n%i0){coutn/i;return 0;}return 0;
}D - 质数筛
思路
写作素数筛读作开方暴力直接暴力验证每个数是不是质数就行了。
code
#include iostream
#include cstdio
using namespace std;
const int maxn105;int n,a[maxn];bool isp(int x){if(x1)return false;for(int i2;i*ix;i)if(x%i0)return false;return true;
}int main(){cinn;for(int i1;in;i)cina[i];for(int i1;in;i)if(isp(a[i]))couta[i] ;return 0;
}E - Prime Distance
题意
给你两个数 L , U L,U L,U 1 ≤ L U ≤ 2147483647 1\le L U\le 2147483647 1≤LU≤2147483647 且 U − L ≤ 1000000 U-L\le 1000000 U−L≤1000000 。问 L ∼ U L\sim U L∼U 中相邻的两个质数中差值最小和最大的一对质数是什么。
思路
直接跑筛法是跑不动的但是根据一个数 x x x 如果是合数那么一定存在一个小于等于 x \sqrt x x 的质因数的性质可以知道 L ∼ U L\sim U L∼U 中的所有合数最大的最小质因数不会超过 U \sqrt U U 我们直接预处理处理 U \sqrt U U 以内的所有素数然后对每个素数筛掉 L ∼ U L\sim U L∼U 中它的倍数 L ∼ U L\sim U L∼U 中剩下的没有被筛掉的数就是素数。
需要注意当 L 1 L1 L1 时会有一个 1 1 1 不会被筛掉而它既不是素数也不是合数因此需要特判去除。
code
#include iostream
#include cstdio
#include vector
using namespace std;
const int maxn1e55;
typedef long long ll;
const ll inf1e18;ll L,U;int prime[maxn],cnt;
bool tvis[maxn*50];
void Eular(int n){tvis[1]true;for(int i2;cntn;i){if(!tvis[i])prime[cnt]i;for(int j1,pprime[1];jcnt i*pmaxn*50;pprime[j]){tvis[i*p]true;if(i%p0)break;}}
}int main(){Eular(1e5);while(cinLU){vectorbool vis(U-L5);if(L1)vis[0]true;for(ll i1,pprime[1];icnt p*pU;pprime[i])for(ll jmax((Lp-1)/p,2ll);j*pU;j)vis[j*p-L]true;ll dmiinf,dmx0,l1,r1,l2,r2;for(ll i0,lst-1;iU-L;i){if(!vis[i]){if(~lst){if(i-lstdmi){dmii-lst;l1lst;r1i;}if(i-lstdmx){dmxi-lst;l2lst;r2i;}lsti;}else lsti;}}if(dmx)printf(%lld,%lld are closest, %lld,%lld are most distant.\n,Ll1,Lr1,Ll2,Lr2);else printf(There are no adjacent primes.\n);}return 0;
}F - 线性筛素数
思路
素数筛板子 p r i m e prime prime 数组中记录的就是从 1 ∼ n 1\sim n 1∼n 的所有素数 p r i m e [ k ] prime[k] prime[k] 就是第 k k k 大的素数。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1e75;int n,q;int prime[maxn],cnt;
bool vis[maxn*10];
void Eular(int n){for(int i2;in;i){if(!vis[i])prime[cnt]i;for(int j1,pprime[1];jcnt i*pn;pprime[j]){vis[i*p]true;if(i%p0)break;}}
}int main(){cinnq;Eular(n);for(int i1,k;iq;i){cink;coutprime[k]endl;}return 0;
}G - 又是毕业季II
思路
好题。洛谷 P1414 又是毕业季II看不懂可以去题解区翻题解看
取出 k k k 个数的最大公因数我们算一遍 看 看 看 个人的最大公因数是 k ∗ l o g k*log k∗log 次数的再枚举选择数…不用想了复杂度爆炸。
那怎么得到 k k k 个人的最大公因数。如果我们知道前 k − 1 k-1 k−1 个人的最大公因数如果第 k k k 个人有因数是这个最大公因数那么最大公因数不变否则是更小的需要所有人都有的因数。
嗯如果我们一开始就对每个数标记一下以它为因数的人有几个不就好了假设记录数组叫 v i s vis vis。这样处理一下的话如果我们找 k k k 个人的最大公因数就直接在 1 ∼ i n f 1 0 6 1\sim inf10^6 1∼inf106 中找最大的 i i i满足 v i s [ i ] ≥ k vis[i]\ge k vis[i]≥k 即可。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1e45;
const int maxf1e65;int n,vis[maxf];//是i的倍数的有多少个 int ans[maxn];int main(){cinn;for(int i1,t;in;i){cint;for(int p1;p*pt;p)if(t%p0){vis[p];if(p*p!t)vis[t/p];}}for(int i1e6;i1;i--)if(!ans[vis[i]])ans[vis[i]]i;for(int in,mx;i1;i--){mxmax(mx,ans[i]);ans[i]mx;}for(int i1;in;i)coutans[i]endl;return 0;
}H - 快速幂
思路
快速幂板题
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;ll a,b,p;ll qpow(ll a,ll b,ll mod){ll basea%mod,ans1;while(b){if(b1){ans*base;ans%mod;}base*base;base%mod;b1;}return ans;
}int main(){cinabp;printf(%lld^%lld mod %lld%lld\n,a,b,p,qpow(a,b,p));return 0;
}I - Carmichael Numbers
题意
Alvaro 认为与传统海鲜饭相比加密海鲜饭的主要优势在于除了你自己没人知道你吃的是什么。
一个合数如果能够通过费马素性检验 a n m o d n a a^n\ mod\ na an mod na就认为他是个一个 C a r m i c h a e l n u m b e r Carmichael\ number Carmichael number。
现在给你一个数问你它是不是 C a r m i c h a e l n u m b e r Carmichael\ number Carmichael number
思路
可以先把合数筛出来。如果给的是合数再进行一下费马素性检验如果都能通过就输出 C a r m i c h a e l n u m b e r Carmichael\ number Carmichael number。
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;
const int maxn65005;int n;int prime[maxn],cnt;
bool vis[maxn];
void Eular(int n){vis[1]true;for(int i2;in;i){if(!vis[i])prime[cnt]i;for(int j1,pprime[1];jcnt i*pn;pprime[j]){vis[i*p]true;if(i%p0)break;}}
}ll qpow(ll a,ll b,ll mod){ll basea%mod,ans1;while(b){if(b1){ans*base;ans%mod;}base*base;base%mod;b1;}return ans;
}int main(){Eular(65000);while(cinn,n){if(!vis[n]){printf(%d is normal.\n,n);continue;}bool ftrue;for(int i2;in;i){if(qpow(i,n,n)!i){ffalse;//不满足素性检验 break;}}if(f)printf(The number %d is a Carmichael number.\n,n);else printf(%d is normal.\n,n);}return 0;
}J - 因子和
思路
洛谷 P1593 因子和
首先需要知道一个数 a a a 的所有因数和是多少。把 a a a 质因数分解得到 a p 1 c 1 ∗ p 2 c 2 ∗ p 3 c 3 ∗ ⋯ ∗ p m c m ap_1^{c_1}*p_2^{c_2}*p_3^{c_3}*\dots*p_m^{c_m} ap1c1∗p2c2∗p3c3∗⋯∗pmcm 那么它的所有因数的和就是 s u m ( 1 p 1 p 1 2 ⋯ p 1 c 1 ) ⋅ ( 1 p 2 p 2 2 ⋯ p 2 c 2 ) ⋅ ⋯ ⋅ ( 1 p m p m 2 ⋯ p m c m ) sum(1p_1p_1^2\dotsp_1^{c_1})\cdot(1p_2p_2^2\dotsp_2^{c_2})\cdot\\\dots\cdot (1p_mp_m^2\dotsp_m^{c_m}) sum(1p1p12⋯p1c1)⋅(1p2p22⋯p2c2)⋅⋯⋅(1pmpm2⋯pmcm)
这个式子可以这样理解我们从第一个括号里随便取一项和第二个括号里随便取一项以此类推一直取到最后一个括号这样就可以得到一个因数。因数一共有 ∏ i 1 m ( c i 1 ) \prod_{i1}^{m}(c_i1) ∏i1m(ci1) 项也正好是这些选取方案取法和因数一一对应。
那么 a b a^b ab 的因数和就是 s u m ( 1 p 1 p 1 2 ⋯ p 1 c 1 ⋯ p 1 b ∗ c 1 ) ⋅ ( 1 p 2 p 2 2 ⋯ p 2 b ∗ c 2 ) ⋅ ⋯ ⋅ ( 1 p m p m 2 ⋯ p m b ∗ c m ) sum(1p_1p_1^2\dotsp_1^{c_1}\dotsp_1^{b*c_1})\cdot(1p_2p_2^2\dotsp_2^{b*c_2})\cdot\\\dots\cdot (1p_mp_m^2\dotsp_m^{b*c_m}) sum(1p1p12⋯p1c1⋯p1b∗c1)⋅(1p2p22⋯p2b∗c2)⋅⋯⋅(1pmpm2⋯pmb∗cm)
第一个括号内是一个等比数列首项为1公比为 p 1 p_1 p1。因此第一个括号内的内容的总和 1 ∗ ( 1 − p 1 b ∗ c 1 1 ) 1 − p 1 p 1 b ∗ c 1 1 − 1 p 1 − 1 \dfrac {1*(1-p_1^{b*c_11})}{1-p_1}\dfrac {p_1^{b*c_11}-1}{p_1-1} 1−p11∗(1−p1b∗c11)p1−1p1b∗c11−1。对 p 1 b ∗ c 1 1 p_1^{b*c_11} p1b∗c11 求快速幂对 p 1 − 1 p_1-1 p1−1 算逆元就能快速求解了对一个数处理出它所有的质因数和对应个数每个质因数用这个过程算出答案结果累乘起来即可。
不过 p 1 − 1 p_1-1 p1−1 可以计算逆元的前提条件是 p 1 − 1 ≢ 0 ( m o d 9901 ) p_1-1\not\equiv0\pmod {9901} p1−1≡0(mod9901)因此当 p 1 ≡ 1 ( m o d 9901 ) p_1\equiv1\pmod {9901} p1≡1(mod9901) 时的情况单独处理发现原式子中这个数就等于 b ∗ c 1 1 b*c_11 b∗c11 。
注意 a 0 a0 a0 的情况需要特判。
code
#include iostream
#include cstdio
#include vector
using namespace std;
typedef long long ll;
const ll mod9901;
#define pii pairint,intll a,b;
vectorpii t;ll qpow(ll a,ll b){b%mod-1;ll basea%mod,ans1;while(b){if(b1){ans*base;ans%mod;}base*base;base%mod;b1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}int main(){cinab;if(a0){cout0endl;return 0;}for(int i2,cnt;i*ia;i){if(a%i0){cnt0;while(a%i0){a/i;cnt;}t.push_back(pii(i,cnt));}}if(a1)t.push_back(pii(a,1));ll ans1;for(auto x:t){ll px.first,cx.second;if(p%mod!1)ansans*(qpow(p%mod,b*c1)-1)%mod*inv(p-1)%mod;else ansans*(b*c1)%mod;}cout(ans%modmod)%mod;return 0;
}
