CF GYM106049 G [构造][数论]

Problem - G - Codeforces

题目大意为将1~n 分为几个连续的区间 然后每个区间的乘积记作pi 求gcd(pi......)的最小值

对于一个长度为v的数组 他的乘积为num1(num1+1)(num1+2)....(num1+v-1) 这个乘积一定是v!的倍数 我们可以利用组合数证明 设组合数c(num1+v-1,v) 即num1(num1+1)(num1+2)....(num1+v-1)/v! 组合数是整数 所以分母一定是分子的乘积 那么就一定是倍数

求所有区间的公约数 等价于 求所有区间长度的阶乘的最大公约数 也等价于求最小区间长度的公约数 那么我们只需要构造出一个最小的区间即可

代码如下

#include <bits/stdc++.h> using namespace std; const int mod=998244353; void solve(){ long long n,l,r; cin>>n>>l>>r; long long num=n/l; if(num*r<n){ cout<<-1<<'\n';return; }else { vector<int>ans; for(int i=1;i<=num;i++){ long long len=max(l,n-(num-i)*r); n-=len; ans.emplace_back(len); } long long res=1; for(int i=1;i<=ans[0];i++){ res=1LL*res*i%mod; } cout<<num<<' '<<res<<'\n'; int cur=1; for(auto x:ans){ cout<<cur<<' '<<cur+x-1<<'\n'; cur+=x; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;cin>>t; while(t--)solve(); return 0; }