HDU 5710 Digit-Sum （构造）

Problem Description

Let S(N) be digit-sum of N, i.e S(109)=10,S(6)=6. If two positive integers a,b are given, find the least positive integer n satisfying the condition a×S(n)=b×S(2n). If there is no such number then output 0.

Input

The first line contains the number of test caces T(T≤10). The next T lines contain two positive integers a,b(0

Output

Output the answer in a new line for each test case.

解题思路

考察 S(n) 与 S(2n) 的关系，可以得到，对于组成 n 的每一位数 x ，其对 S(n) 的贡献为 x，对 S(2n) 的贡献为 2x(if x < 4) ， 2x−9(if x >= 5) 。

因此，假设 n 中含有 >=5 的数字 L 个。 S(2n)=2×S(n)−9×L 成立。结合题目要求的等式 a×S(n)=b×S(2n) ，则：

a×S(n)=b×(2×S(n)−9×L)

⟺a×S(n)=2b×S(n)−9×b×L

⟺(2b−a)×S(n)=9×b×L

⟺S(n)L=9×b2b−a

由于 S(n) , L, 9×b , 2b−a 均为整数，故 S(n)=k⋅(9×b) ， L=k⋅(2b−a) 。同时，由于要求 n 最小，可知 k 取 1 时最小。

在已有 S(n) 以及 L 的情况下，如何求 n ？

首先构造长为 L ，每个字符均为 5 （由于 L 个数字必须 >= 5）的字符串，同时 S(n)−=5×L 。对于多余的 S(n) ，为使得 n 尽可能小（即串长最小，大的数字尽可能向个位数靠拢）。故优先将串尾的字符增长到 9 。

若长为 L 的字符串已经全部为 9 。此时不得不增加串长，则优先在串首增加 4 （不在 L 个数字中的均 <= 4），直到 S(n) 全部用尽。

需要注意，当 a>2×b 以及 5×a<b 时，不可构造，输出 0

代码

#include<bits/stdc++.h> using namespace std; int main() { int T, a, b, L, sn, GCD, val; scanf("%d",&T); while(T--) { scanf("%d %d",&a,&b); if(a > 2*b || 5*a < b) printf("0\n"); else { L = 2*b-a, sn = 9*b; GCD = __gcd(L, sn); L /= GCD, sn /= GCD; string ans = string(L, '5'); sn -= 5*L; for(int i=ans.size()-1;i+1;i--) { val = min(sn, 4); ans[i] += val; sn -= val; } while(sn) { val = min(sn, 4); ans = char(val+'0') + ans; sn -= val; } printf("%s\n", ans.c_str()); } } }