中石油 问题 A: 联通数(数学)

题目链接

题意:

给出你一个\(n\)和\(k(k>=1,k<=9)\)我们可以减\(kk,kkk,kkkk....\)
问最后能否减成零

思路:

先举个例子说明一下题意:假设n=10750,k=8那么我们 可以减的是\(88,888,888,8888....\)
我们可以看出\(88\)可以认为成最小的单位,因为\(888,8888,88888....\)都可以转化成\(88\)
888 = 88*10+8
8888 = 88*100+88
88888 = 88*100+888
我们可以看出来奇数位的\(kkk\)需要加上一个8才能正常生成.进而我们得到yu=n%kk,yu必须整除k这是我们的第一个条件.
第二个条件:我们光把余下的8整出来了,还需要888来接受,所以\(num=n/kk/10\),num必须是大于yu/k的这样才有接受的对象.为什么要除10那因为不除10,num的个位代表kk,但kk是不需要k的,最小需要k的单位是kkk所以我们需要除以10.

就拿我们上面举的例子: yu=16,num=12,8|16能够整除第一个条件符合.12>16/8二个条件符合.
有人要问了,12个880拿走两个变成两个888,还有10个880那也不符合呀,首先我们看880跟88的关系,是不是可以转化成10个88,88是最小的单位,那么10个880也就转化成100个88,这样不都转化成符合条件的吗?

void solve()
{
    scanf("%lld%lld", &n, &k);
    ll tmp = k;
    k = k * 10 + k;
    ll num = n / k;
    ll sum = n % k;
    num = num / 10;
    if(num * tmp >= sum && sum % tmp == 0) puts("YES");
    else puts("NO");
}
上一篇:旅行商问题的动态规划解法


下一篇:upc2021个人训练赛第22场A. 联通数(思维)