天津河北区做网站,小白怎么做无货源电商,蜜糖直播,网站维护包括哪些工作今天写了几道题目
最近#xff0c;一年级学生马克西姆学习了科拉兹猜想#xff0c;但他在讲课时没有太注意#xff0c;所以他认为猜想中提到了以下过程#xff1a;
有一个变量 $$$x$$$ 和一个常数 $$$y$$$ 。下面的操作要执行 $$$k$$$ 次#xff1a;
- 将 $$$x$$$ 增加…今天写了几道题目
最近一年级学生马克西姆学习了科拉兹猜想但他在讲课时没有太注意所以他认为猜想中提到了以下过程
有一个变量 $$$x$$$ 和一个常数 $$$y$$$ 。下面的操作要执行 $$$k$$$ 次
- 将 $$$x$$$ 增加 $$$1$$$ 然后 - 当数字 $$$x$$$ 能被 $$$y$$$ 整除时再除以 $$$y$$$ 。
请注意这两个操作都是在一次操作中依次进行的。
例如如果数字 $$$x 16$$$ 、 $$$y 3$$$ 和 $$$k 2$$$ 那么经过一次运算后 $$$x$$$ 变成了 $$$17$$$ 而经过另一次运算后 $$$x$$$ 变成了 $$$2$$$ 因为加一后 $$$x 18$$$ 可以被 $$$3$$$ 整除两次。
鉴于初始值为 $$$x$$$ 、 $$$y$$$ 和 $$$k$$$ 马克西姆想知道 $$$x$$$ 的最终值是多少。
思路是先凑到y的倍数在除y考虑到时间的问题所以基于二分的思想设置了一个s每次对自己平方再判断能不能整除复杂度从n降到了logn一直除到ab,再凑到a等于b再除就是1那么就是对剩下的c的部分对b-1取余再加一即为答案。
#includebits/stdc.h
#includealgorithm
#define ll long long
#define max_int 2147483647
#define max_ll 9223372036854775807
using namespace std;
int main()
{ios::sync_with_stdio(false);cin.tie(0);int all;cinall;while(all--){ll a,b,c;cinabc;int bo1;while(c){ll yub-a%b;ll sb,s2b*b;if(yuc){c-yu;ayu;}else{coutacendl;bo0;break;}while(a%b0){sb;while(a%s0){s2s;s*s;}a/s2;}if(ab){if(cb-a){c-b-a;}else{coutacendl;bo0;break;}if(c0){cout1endl;bo0;break;}coutc%(b-1)1endl;bo0;break;}//if(bo) coutaendl;//else break;}if(bo) coutaendl;}return 0;
}关键在组合数的拆分和前缀和处理以及取模的问题。
#includebits/stdc.h
#define ll long long
#define max_int 2147483647
#define max_ll 9223372036854775807
using namespace std;
vectorvectorintq(2001,vectorint(2001));
vectorvectorintp(2001,vectorint(2001));
void solve(int k){q[1][1]1;for(int i0;i2000;i){q[i][0]1;}for(int i2;i2000;i){for(int j1;ji;j){q[i][j](q[i-1][j]q[i-1][j-1])%k;}}for(int i2;i2000;i){for(int j1;ji;j){p[i][j]p[i-1][j]p[i][j-1]-p[i-1][j-1];if(q[i][j]0) p[i][j]1;}p[i][i1]p[i][i];}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t,k,n,m;cintk;solve(k);for(int i0;it;i){cinnm;if(mn) mn;coutp[n][m]endl;}return 0;
}
