icontofig | 发布于 2019-11-06 22:11:12 | 阅读量 352 | 数论 数学
发布于 2019-11-06 22:11:12 | 数论 数学
BZOJ 2242 SDOI2011 计算器
题解第一问快速幂 第二问是扩展欧几里得算法求不定方程 第三问使用BSGS算法求离散模对数 三个函数直接看代码吧……纯板子题…… 代码#include <bits/stdc++.h> using namespace std; typedef long long ll; ll get_num(){ ll num = 0; char c; bool flag = false; while((c = getchar()) == ' ' || c == '\r' || c == '\n'); if(c == '-') flag = tr
继续阅读
icontofig | 发布于 2019-10-05 21:34:07 | 阅读量 335 | DP bitset 数论
发布于 2019-10-05 21:34:07 | DP bitset 数论
牛客国庆欢乐赛5 2017四川省赛 K-2017Revenge bitset加速dp、原根
题目大意给出n个数,要你从中选出一些数,使得他们的乘积mod 2017的余数为r,问总方案数mod 2的值。 题解对于一些数的乘法,我们可以用log把他转化乘加法。 但是是在模意义下,就是需要离散模对数了。 这时候我们要求2017的原根,2017的原根是5,我们就可以自然而然的把原来的所有数都化为他们的离散模对数了。 首先如果数据范围很小,我们该怎么写呢? 那么我们可以用dp[i][j]表示当前为第枚举到第i个数,选出的前面的(包括i)所有数的乘积的离散模对数为j的方案数。 那么dp方程就很容易能够想到了: dp[i][j] = dp[i-1][j] + (dp[i-1][(j-lg[a[i]
继续阅读
icontofig | 发布于 2019-08-26 00:04:09 | 阅读量 476 | 数论
发布于 2019-08-26 00:04:09 | 数论
2019 CCPC网络赛 1005 huntian oy 杜教筛
题目大意 给定n,a,b,其中a,b保证互质m,求 f(n,a,b)=&#x2211;i=1n&#x2211;j=1igcd(ia&#x2212;ja,ib&#x2212;jb)[gcd(i,j)==1]'>f(n,a,b)=∑ni=1∑ij=1gcd(ia−ja,ib−jb)[gcd(i,j)==1]f(n,a,b)=∑i=1n∑j=1igcd(ia−ja,ib−jb)[gcd(i,j)==1]f(n,a,b) = \sum_{i = 1} ^ {n}\sum_{j = 1} ^ {i} gcd(i^a-j^a,i^b - j^b)[gcd(i,j)
继续阅读
icontofig | 发布于 2019-06-04 00:08:00 | 阅读量 399 | 数论 同余线性方程
发布于 2019-06-04 00:08:00 | 数论 同余线性方程
POJ 青蛙的约会 扩展欧几里得解同余线性方程
题解青蛙的世界真是简单啊,而人类就不一样了QAQ 扯远了扯远了…… 对这个题目进行比较小的数学建模,我们可以得到这样一个式子 然后我们移一下项,可以得到  我们要求解的就是t的最小值。 上式可以转化以下一元二次不定方程:  然后我们都清楚一元二次不定方程的解法无非就是扩展欧几里得…… 其中如果gcd((m-n),l)不能整除(y-x)的话,此方程则是无解的,直接输出Impossible。 否则的话,就利用扩展欧几里得去计算t。 先对两边式子的系数同时除以gcd((m-n),l),利用扩展欧几里得算法解出a*t’ + b*p‘ = 1的解中的t’,然后再乘(y-x)/g
继续阅读