#include using namespace std; typedef long long LL; LL a = 482333897982347239LL; LL b = 557432748293424892LL; LL k = 1389472389742429877LL; //同余 (b-a) % mod = b*2 % mod void test(){ LL mod = a + b; cout<<(b-a) % mod<>= 1; } return ans; }//快速幂 LL mpow(LL x,LL y,LL p){ LL ans = 1LL; while(y){ if(y & 1LL) ans = mmul(ans,x,p); x = mmul(x,x,p); y >>= 1; } return ans; }int main(){ LL mod = a + b; //首先 c + d = 2*a + b - a=a + b = mod LL ans = mmul(a,mpow(2LL,k,mod),mod); //d = b - a = b - (mod - b) = 2*b - mod = 2*b %mod，所以 b-a 也就等价于 b*2,等价后a与b交不交换都无所谓(因为后面的操作都是*2) printf("%lld\n",min(ans,mod-ans)); //结果确保A更小,A可能是ans 也可能是mod-ans(b) return 0; } //383513242709218605

蒜头君有n个数，他想要从中选出k个数，使得它们的最大公约数最大。
请你求出这个最大的最大公约数。

输入格式
第一行输入两个整数 。
第二行输入 个整数 。

输出格式
输出一个整数。

数据范围

文章图片

样例输入1
4 3
2 4 8 3
样例输出1
2

样例输入2
4 2
4 8 6 6
样例输出1
6

#include using namespace std; typedef long long ll; ll ans = 1; ll gcd(ll a,ll b){ if(b==0) return a; return gcd(b,a%b); }const int maxn = 1e6+10; int n,k; int a[maxn]; /* dfs暴搜过30%数据 *//* 不确定的dp状态转移方程:dp[i][k] = max(dp[i][k],gcd(dp[j n+1) return; if(have > k+1) return; if(have == 1){ dfs(cur+1,have,_gcd); dfs(cur+1,have+1,a[cur]); }else{ dfs(cur+1,have,_gcd); dfs(cur+1,have+1,gcd(a[cur],_gcd)); }}int main(){ scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) scanf("%d",&a[i]); dfs(1,1,0); printf("%lld\n",ans); return 0; }

#include using namespace std; typedef long long ll; const int N = 1e6 + 7; const int mod = 1e9 + 7; int a[N+10]; int main(){ int n,k,x; memset(a,0,sizeof(a)); scanf("%d%d",&n,&k); for(int i=0; i= k) ans = i; //比k大 那么选出k个数 他们的gcd就是当前的i } printf("%d\n",ans); return 0; }

#include using namespace std; const int mod = 1046513837; int n,m,f[200500]; int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }void merge(int a,int b){ int x = find(a); int y = find(b); if(x != y ) f[x] = y; }int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) f[i] = i; long long ans = 1; for(int i=1 ; i<=m; i++){ int a,b; scanf("%d%d",&a,&b); int x = find(a), y = find(b); if(x == y){//这里如果 两个点祖先一样 说明找到环了 ans <<= 1; if(ans > mod) ans -= mod; }else merge(a,b); printf("%lld\n",ans-1); } return 0; }

#include using namespace std; const int maxn = 3*1e6+5; int n; int m[maxn]; int vis[maxn]; int ans = 0; /* 枚举l~r区间 枚举i~j区间 */int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&m[i]); for(int l=1; l<=n; l++){ for(int r=l+1; r<=n; r++){ bool flag = false; for(int a=1; a<=n; a++){ for(int b=a; b<=n; b++){ for(int c=b+1; c<=n; c++){ for(int d=c; d<=n; d++){ bool flag2 = true; for(int i=1; i<=n; i++) vis[i] = 0; for(int i=a; i<=b; i++) vis[m[i]] = 1; for(int i=c; i<=d; i++) vis[m[i]] = 1; for(int i=l; i<=r; i++){ if(vis[i] == 0){ flag2 = false; break; } } if(flag2 && r-l+1 == b-a+1 + d-c+1){ ans++; flag = true; //cout<<"l = "<=1; i--) { x=nt[i]; if (p[x+1]i) work(1,1,n,i,p[x-1]-1,1); if (p[x+1]>i && p[x-1]i && p[x-1]>i) { k1=p[x+1]; k2=p[x-1]; if (k1>k2) swap(k1,k2); work(1,1,n,i,k1-1,1); work(1,1,n,k2,n,-1); } upans(1,1,n,i,n); } printf("%lld",ans-n); return 0; }