小苯的前缀gcd构造
时间限制：1秒 空间限制：1024M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
对于一个长度为n nn的数组{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n\}{a1,a2,…,an}，小苯先定义f ( i ) = g c d ( a 1 , a 2 , … , a i ) [ 1 ] f(i)=gcd(a_1,a_2,…,a_i)^{[1]}f(i)=gcd(a1,a2,…,ai)[1]，基于此，再定义数组的权值为：
∑ j = 1 n f ( j ) ∑_{j=1}^nf(j)∑j=1nf(j)
现在，小红想让小苯构造一个长为n nn且所有元素都在[ 1 , m ] [1,m][1,m]之内的数组，满足其权值恰好为x xx。
请你帮帮小苯。
【名词解释】
g c d [ 1 ] gcd^{[1]}gcd[1]：即最大公因数，指多个整数共有因数中最大的一个。例如，12 1212、18 1818和30 3030的公因数有1 , 2 , 3 , 6 1,2,3,61,2,3,6，其中最大的因数是6 66，因此g c d ( 12 , 18 , 30 ) = 6 gcd(12,18,30)=6gcd(12,18,30)=6。特别地，定义g c d ( x ) = x gcd(x)=xgcd(x)=x。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 10 ) T(1≦T≦10)T(1≦T≦10)代表数据组数，每组测试数据描述如下：
第一行输入三个整数n , m , x ( 1 ≦ n , m ≦ 50 ; 1 ≦ x ≦ n × m ) n,m,x(1≦n,m≦50; 1≦x≦n×m)n,m,x(1≦n,m≦50;1≦x≦n×m)。
除此之外，保证单个测试文件的n nn之和、m mm之和不超过50 5050。
输出描述：
对于每一组测试数据，新起一行。如果不存在满足条件的数组，直接输出− 1 −1−1；否则，在一行上输出n nn个整数，代表所构造的数组。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1
输入：
1 5 4 6输出：
2 1 1 1 1说明：
在这个样例中：
- f ( 1 ) = g c d ( a 1 ) = 2 f(1)=gcd(a_1)=2f(1)=gcd(a1)=2；
- f ( 2 ) = g c d ( a 1 , a 2 ) = 1 f(2)=gcd(a_1,a_2)=1f(2)=gcd(a1,a2)=1；
- f ( 3 ) = g c d ( a 1 , a 2 , a 3 ) = 1 f(3)=gcd(a_1,a_2,a_3)=1f(3)=gcd(a1,a2,a3)=1；
- f ( 4 ) = g c d ( a 1 , a 2 , a 3 , a 4 ) = 1 f(4)=gcd(a_1,a_2,a_3,a_4)=1f(4)=gcd(a1,a2,a3,a4)=1；
- f ( 5 ) = g c d ( a 1 , a 2 , a 3 , a 4 , a 5 ) = 1 f(5)=gcd(a_1,a_2,a_3,a_4,a_5)=1f(5)=gcd(a1,a2,a3,a4,a5)=1。
示例2
输入：
1 5 5 4输出：
-1解题思路
本题核心是前缀gcd性质 + 动态规划(DP) + 回溯构造，利用前缀gcd的数学特性解决构造问题。前缀gcd序列满足非递增且后项是前项的约数，基于此设计三维DP：dp[i][g][s]表示前i个元素、第i个前缀gcd为g、总权值和为s的方案是否存在。初始化第一个元素的所有可能值，按gcd约束转移状态。若最终不存在dp[n][g][x]=1则输出-1；若存在，从后往前回溯DP状态，逆推每一步的前缀gcd，直接取当前gcd作为数组元素（满足gcd约束），反转后得到合法数组。数据范围极小，算法高效稳定。
总结
核心逻辑：利用前缀gcd非递增、整除的性质，通过DP判断可行性，回溯构造答案。
关键操作：三维DP状态转移、gcd约束校验、逆序回溯构造数组。
效率保障：严格适配n,m≤50的小数据范围，方案构造简单且满足所有题目要求。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll f[55][55][2550];voidsolve(){ll n,m,x;cin>>n>>m>>x;memset(f,0,sizeof(f));for(ll i=1;i<=m;i++)f[1][i][i]=1;for(ll i=2;i<=n;i++)for(ll j=1;j<=m;j++)for(ll s=1;s<=x;s++)if(f[i-1][j][s])for(ll v=1;v<=j;v++)if(j%v==0&&v+s<=x)f[i][v][v+s]=1;ll c=-1;for(ll i=1;i<=m;i++)if(f[n][i][x]==1)c=i;if(c==-1){cout<<-1<<'\n';return;}vector<ll>ans;ll sum=x;for(ll i=n;i>=1;i--){ans.push_back(c);if(i==1)break;for(ll j=c;j<=m;j+=c)if(f[i-1][j][sum-c]){sum-=c;c=j;break;}}reverse(ans.begin(),ans.end());for(ll i=0;i<n;i++)cout<<ans[i]<<" \n"[i==n-1];}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t=1;cin>>t;while(t--)solve();return0;}
