小苯的前缀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 ) ∑_{j1}^nf(j)∑j1n​f(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​)2f ( 2 ) g c d ⁡ ( a 1 , a 2 ) 1 f(2)gcd⁡(a_1,a_2)1f(2)gcd⁡(a1​,a2​)1f ( 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​)1f ( 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​)1f ( 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序列满足非递增且后项是前项的约数基于此设计三维DPdp[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的小数据范围方案构造简单且满足所有题目要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll f[55][55][2550];voidsolve(){ll n,m,x;cinnmx;memset(f,0,sizeof(f));for(ll i1;im;i)f[1][i][i]1;for(ll i2;in;i)for(ll j1;jm;j)for(ll s1;sx;s)if(f[i-1][j][s])for(ll v1;vj;v)if(j%v0vsx)f[i][v][vs]1;ll c-1;for(ll i1;im;i)if(f[n][i][x]1)ci;if(c-1){cout-1\n;return;}vectorllans;ll sumx;for(ll in;i1;i--){ans.push_back(c);if(i1)break;for(ll jc;jm;jc)if(f[i-1][j][sum-c]){sum-c;cj;break;}}reverse(ans.begin(),ans.end());for(ll i0;in;i)coutans[i] \n[in-1];}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t1;cint;while(t--)solve();return0;}