广西圣泰建设工程有限公司网站,微投票网站,移动 网站 素材,网站备份流程2022河南萌新联赛第#xff08;三#xff09;场#xff1a;河南大学\神奇数字.cpp
//题意#xff1a;给定三个正整数a b c,求x满足满足abc同余x的个数。
//这个考虑同余的性质#xff0c;就是两个数的差去取模为0的数肯定是这两个数的同余数,。因此我们计算三个数两两之…2022河南萌新联赛第三场河南大学\神奇数字.cpp
//题意给定三个正整数a b c,求x满足满足abc同余x的个数。
//这个考虑同余的性质就是两个数的差去取模为0的数肯定是这两个数的同余数,。因此我们计算三个数两两之间差的最大公约数然后直接分解质因数计算gcd的因子个数就是x能够用取到的数量。
#includebits/stdc.h#includeiostream#includealgorithm#includemap#includeset#includequeue#includecstring#includemath.h#includemap#includevector#includestackusing namespace std;#define endl \ntypedef pairint,int pr;#define int long long#define ll long long#define fr(i,l,r) for(int il;ir;i)#define ufr(i,n,z) for(int i n;i z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N 1e610;const int mod998244353,infLONG_LONG_MAX;int n,m;int a[N];int gcd(int a,int b){return !b?a:gcd(b,a%b);}void solve(){int a,b,c;cinabc;if(abac){cout-1\n;return ;}int xgcd(abs(a-b),abs(b-c));vectorintv;for(int i1;i*ix;i){if(x%i0){if(i!x/i)v.push_back(x/i);v.push_back(i);}}sort(v.begin(),v.end());fr(i,0,v.size()-1){coutv[i] ;}cout\n;}signed main(){int t1;cint;while(t--) solve();return 0;}
总结//同余的性质 (就是两个数的差去取模为0的数肯定是这两个数的同余数) //同余式可逐项相加 //同余式可以逐项相乘。 //同余式一边的数可以移到另一边只要改变符号就可以了 //同余式的每一边都可以增加或减去模的任意倍数。 //同余式两边的数如有公约数此公约数又和模互素那么就可以把两边的数除以这个公约数。 //同余式两边的数和模可以同时乘上一个整数。 //同余式两边的数和模可以同时被它们任一公约数除。 //如果同余式对于模m成立那么它对于m的任意约数相等的模d也成立。 //如果同余式一边上的数和模能被某个数除尽则同余式的另一边的数也能被这个数除尽。 //同余式一边上的数与模的最大公约数等于另一边上的数与模的最大公约数 2022河南萌新联赛第三场河南大学\逆序对计数.cpp
//题意给定长度为n的排列0n6000,每次询问为如果将l,r翻转则逆序对的个数
//思路 对于一个排列, 如果区间反转, 逆序数等于区间中所有的对数减去当前的逆序对数, 即原本的正序对变为逆序对, 原本的逆序对变为正序对。
//改变区间在整个区间的位置不重要逆序对的增减只会在区间进行
/* #includebits/stdc.h#includeiostream#includealgorithm#includemap#includeset#includequeue#includecstring#includemath.h#includemap#includevector#includestackusing namespace std;#define endl \ntypedef pairint,int pr;#define int long long#define ll long long#define fr(i,l,r) for(int il;ir;i)#define ufr(i,n,z) for(int i n;i z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N 1e610;const int mod998244353,infLONG_LONG_MAX;int n,m;int a[N];int s[6010][6010];int change(int l,int r){int lenr-l1;int xlen*(len-1)/2;return x-2*s[l][r];}void solve(){cinn;fr(i,1,n){cina[i];}int res0;fr(i,1,n){ //预处理所有l,r的逆序数个数fr(j,1,i){s[j][i]s[j][i-1];}int cnt0;ufr(j,i-1,1){if(a[j]a[i]){cnt;res;}s[j][i]cnt;}}cinm;while(m--){int l,r;cinlr;coutreschange(l,r)\n;}}signed main(){int t1;// cint;while(t--) solve();return 0;} *///树状数组做法#includebits/stdc.h#includeiostream#includealgorithm#includemap#includeset#includequeue#includecstring#includemath.h#includemap#includevector#includestackusing namespace std;#define endl \ntypedef pairint,int pr;#define int long long#define ll long long#define fr(i,l,r) for(int il;ir;i)#define ufr(i,n,z) for(int i n;i z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N 1e610;const int mod998244353,infLONG_LONG_MAX;int n,m;int a[N];int t[N];int f[6010][6010];void add(int x){for(int ix;in;ii-i){t[i]1;}}int query(int x){int ans0;for(int ix;i;i-i-i){anst[i];}return ans;}void solve(){cinn;fr(i,1,n){cina[i];}fr(i,1,n){fr(j,i,n){f[i][j]f[i][j-1](j-i-query(a[j])); //(j-i-query(a[j])即区间-正序对个数add(a[j]);}fr(j,1,n){t[j]0;}}cinm;int resf[1][n];while(m--){int l,r;cinlr;coutres(r-l1)*(r-l)/2-2*f[l][r]\n;}}signed main(){int t1;// cint;while(t--) solve();return 0;}
P1045 [NOIP2003 普及组] 麦森数(高精度快速幂) 题意输入P(1000p3100000)输出2^p-1的位数及最后500位数
#includeiostream
#includemath.h
#includecstring
using namespace std;
int f[1001], p, res[1001], sav[1001];//乘法要开两倍长度
void result_1() {memset(sav, 0, sizeof(sav));for (register int i 1; i 500; i 1)for (register int j 1; j 500; j 1)sav[i j - 1] res[i] * f[j];//先计算每一位上的值不进位for (register int i 1; i 500; i 1){sav[i 1] sav[i] / 10;//单独处理进位问题不容易出错sav[i] % 10;}memcpy(res, sav, sizeof(res));//cstring库里的赋值函数把sav的值赋给res
}
void result_2() {memset(sav, 0, sizeof(sav));for (register int i 1; i 500; i 1)for (register int j 1; j 500; j 1)sav[i j - 1] f[i] * f[j];for (register int i 1; i 500; i 1){sav[i 1] sav[i] / 10;sav[i] % 10;}memcpy(f, sav, sizeof(f));
}
int main() {cin p;cout int(log10(2) * p 1) \n; //2^p-1,2^p的位数res[1] 1;f[1] 2;while (p) {if (p % 2 1) {result_1();}result_2();p 1;}res[1] - 1;for ( int i 500; i 1; i--)//注意输出格式50个换一行第一个不用if (i ! 500 i % 50 0)printf(\n%d, res[i]);else printf(%d, res[i]);return 0;
}
数位dp
(最高位限制记忆化搜索枚举位的大小前导0)
洛谷P2657 [SCOI2009] windy 数
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道在A和B之间包括A和B总共有多少个windy数
#includeiostream
#includecstring
using namespace std;
int num[12], dp[12][12];
int dfs(int pos, int pre, int limit, int lead) {int ans 0, i, up;if (pos -1) //搜完return 1; //用作计数if (!limit dp[pos][pre] ! -1 !lead)//没有最高位限制已经搜过了,并且没有前导0return dp[pos][pre]; //记忆化搜索up limit ? num[pos] : 9;//当前位最大数字 for (i 0; i up; i) {//从0枚举到最大数字 if (lead) {//有前导0不受限制 ans dfs(pos - 1, i, limit i up, lead i 0);}else if (i - pre 2 || i - pre -2)//无前导0受限 ans dfs(pos - 1, i, limit i up, lead i 0);}if (!limit !lead)//没有最高位限制且没有前导0时记录结果 dp[pos][pre] ans;return ans;
}
int solve(int x) {int pos 0;while (x) {num[pos] x % 10;x / 10;} //按位储存return dfs(pos - 1, -1, 1, 1);
}
int main() {ios::sync_with_stdio(false);int lt, rt;cin lt rt;memset(dp, -1, sizeof(dp));cout solve(rt) - solve(lt - 1)\n;return 0;
}
