段三园的小迷弟

题解

心得(37) 未归档(1) 模板题(7) 读书笔记(2)

/ 注册

全部文章 / 题解（共15篇）

P3951 小凯的疑惑，同余

因为a,b互素，所以gcd（a，b）=1，所以不定方程ax+by=可以等于任何数，任何数%1==0 但是如果x，y有一个是负数就不符合题意设a<b，答案为x 则： x=ma (mod b) (1<=m<=b-1) x=ma+n...

取余求模数论

2020-02-03

0 546

p2158[SDOI2008]仪仗队,欧拉函数

把这个看成是一个坐标，左下是原点，任何一个（x，y）和原点连线就是斜率k 能看见的人x和y都是互质的（除x，y轴）所以只要遍历1~n-1求和欧拉函数phi，然后加上3个没加到的点注意加上三个没加到的是当n>2时候，所以要特判 #include <...

数论欧拉函数

2019-11-02

0 600

SP19786GGD，gcd+数论

gcd（a，b）=g a=k1 g , b=k2 g 且gcd（k1，k2）=1 gcd（a，...

因数约数数论

2019-11-02

0 601

cf1038BNon-CoprimePartition，数论

1~n的和：（1+n）n/2 所以和在1~n中是n或者n/2的倍数提出n（因为不是每个n都有n/2）有：（n-1）n/2 当n为奇数时：（n-1）是偶数，可以被2整除；只有n=1时例外，提出n后0和1gcd不满足，分析除本选法其他方法也没法实现当n为偶数时：n和n/2除因...

因数约数数论思维题

2019-10-25

0 478

cf983a Finite or not，数论+模拟

一个分数是否可以除尽首先约分，1/2, 1/125可以除尽的原因是：十进制10=2*5->1/2,1000=2^3*5^3->1/125也就是10包括了2,125的所有质因数 b进制下，分母q是有限小数的充分条件是b有q的所有质因数因此，这个问题就转化为了：...

因数约数数论

2019-10-20

0 552

p4549【模板】裴蜀定理（模板）

对于任意正整数x，y，一定存在整数a，b，使得： ax+by=gcd(x,y); 这里记得绝对值下 #include <bits/stdc++.h> using namespace std; int ...

因数约数模板数论

2019-10-19

0 485

uva11388GCD LCM

我们先来看下什么情况是-1（无解）：随便两个数3,4；就是无解，为什么因为要lcm%gcd=0，所以无解的情况就出来了那么最小怎么满足呢 x和y必须是a的倍数，那么x最小就是a，那么此时y=lcm

因数约数数论

2019-10-19

0 487

p1835素数密度，埃氏筛法（大数小区间的素数个数）

这个是大数（1e9）的小区间（1e6）的素数个数埃氏n ln n大约2e7 预测400ms 线性打表2~根号n for i：素数表 for j:l~r中i最小的倍数~n &...

数论质数

2019-10-17

0 723

P2563 [AHOI2001]质数和分解，质数+dp背包

f[n]+=f[n-素数] 正确的代码： #include <bits/stdc++.h> using namespace std; const int N=207,INF=203; int cnt,dp[N],n; ...

模拟数论枚举质数打表完全背包 dp

2019-10-08

0 594

p5440【XR-2】奇迹，模拟+打表

伪代码先把所有符合条件的年月日找出 while (询问次数){ 输入询问串 for 遍历每一个找出的年月日 ...

模拟数论枚举打表质数

2019-10-08

0 833