#P18563. Master of Modular Arithmetic
Master of Modular Arithmetic
Master of Modular Arithmetic
“拜托……我已经厌倦了那些数一些莫名其妙的东西、最后再对一个大质数取模的计数题。能不能来点不一样的?”
小青鱼热爱模运算,也精通处理模运算的技巧。为了检验你是否真正理解模运算的美妙,小青鱼给你一个由 个正整数组成的序列 。
你最多可以进行 次下列操作:
- 选择整数 ,满足 。
- 选择两个不同的下标 ,满足 且 。
- 更新 ,同时更新 。
小青鱼希望你通过这些操作,把序列 变成另一个序列 。判断是否可能,并在可能时输出方案。
这里 是除以正整数 的非负余数。原题没有给中间整数设置上限;初始和目标数值的限制不表示操作过程受同一上界限制。
输入格式
输入含多组测试。第一行是整数 (),表示测试组数。对每组测试:
- 第一行一个整数 ()。
- 第二行 个整数 (),表示初始序列。
- 第三行 个整数 (),表示目标序列。
保证所有测试的 之和不超过 。
输出格式
对于每组测试:如果无法在 次操作内把 变成 ,输出一行 No。
否则,首先输出一行 Yes。下一行输出整数 (),表示操作次数。接下来输出 行,每行三个整数 ,按执行顺序描述一次操作,满足题目中的全部要求。可以输出任意合法方案。
原样例
3
2
2 2
1 2
4
4 4 4 4
1 1 1 1
5
1 4 3 2 5
2 4 5 4 1
Yes
5
1 2 10
2 1 19
1 2 7
2 1 3
1 2 2
No
Yes
3
3 4 2
1 3 5
5 1 2
第一组给出的五次操作将 依次变为 、、、、。第三组给出的方案依次得到 、、。