【数学推导】数字变换

清疚 2021-12-15 23:15 276阅读 0赞

## 题目描述 ##

Alice 给了 Bob 一个数 k，求有多少个数 x，满足：从 x 的某个数位（不能是最后一位）后加一个乘号，运算得到一个数 y，使得 x−y=k。

比如：如果 k=123，那么 277 就是一个符合要求的数，因为 277−2×77=123。

Bob 觉得这个问题太难了，希望你可以帮他解决。

## 输入输出格式 ##

输入格式：

一行一个整数 k，意义如上所述。

输出格式：

一行一个整数，表示答案。

## 输入输出样例 ##

输入样例\#1：

123

输出样例\#1：

输入样例\#2：

2333

输出样例\#2：

输入样例\#3：

999999999

输出样例\#3：

--------------------

【题解】：
    这个题目也是通过讲评后我才知道这个怎么做的。
    首先读一遍题目：
    题目需要我们找出所有符合一种 形式的数 以一种形式等于k。
    形式的数是指：X = a*(10^t) + b 
    然后一种形式为： X - a * b = k
    
    根据这个题目我们知道 K 的范围为： 1e9
    我们可以枚举 10^t，t = 1,2,3……9.
    我们设：t = 10^t。
    
    然后有：a*t-a*b=k
    因式分解：(a-1)*(t-b)=k-t
    然后通过这个式子进行分析。
    1、当k-t<0,不存在a,b，因为左边都是整数。
    2、当k-t>0,可以通过根号n枚举所有k-t的因数，然后排序找出对应的a,b。
    3、当k-t==0,由于t>b,∴a=1,然后b可以b<t的任意数。
    注意去重：
    比如100000,可能在讨论（2）时涉及了，然后计算（3）时重复了。
    贴上代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 ll k,ans,A,B,K,a,b,F;
     5 set<ll>Ans;
     6 vector<ll> V;
     7 int main()
     8 {
     9     scanf("%lld",&k);
    10     for(ll t=10 ; t<=INT_MAX ; t*=10 ){
    11         if( k-t > 0 ){
    12             K = k-t;
    13             //printf("%lld %lld \n",t,K);
    14             for(ll i=1 ; i*i<=K ; i++ ) {
    15                 V.push_back( i );
    16                 if( i*i != K ){
    17                     V.push_back( K/i );
    18                 }
    19             }
    20             sort(V.begin(),V.end() );
    21             V.erase( unique( V.begin(),V.end() ), V.end() );
    22             for(auto A:V){
    23                 a = A + 1 ;
    24                 b = t - K/A;
    25                 if( b<t && b>=0 && a*t + b - a*b == k){
    26                     //cout << a*t + b << endl ;
    27                     Ans.insert( a*t + b );
    28                 }
    29             }
    30         }else if ( k-t == 0 ){
    31             F = t ;
    32         }
    33     }
    34     if( F ){
    35         //printf("###\n");
    36         set<ll> ::iterator it1 = lower_bound(Ans.begin(),Ans.end(),F);
    37         set<ll> ::iterator it2 = lower_bound(Ans.begin(),Ans.end(),2*F);
    38         //it2--;
    39         Ans.erase(it1,it2);
    40     }
    41     ans = Ans.size() + F;
    42     printf("%lld\n",ans);
    43     return 0 ;
    44 }

数字变换

转载于:https://www.cnblogs.com/Osea/p/10995118.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211215/1d8e7c45aefe46ab9f1127038b47aead.png