题目描述

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

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 

123

输出样例#1： 

3

输入样例#2：

2333

输出样例#2： 

9

输入样例#3： 

999999999

输出样例#3：

34

---

【题解】： 这个题目也是通过讲评后我才知道这个怎么做的。 首先读一遍题目： 题目需要我们找出所有符合一种 形式的数 以一种形式等于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

1 #include
        
          2 using namespace std; 3 typedef long long ll; 4 ll k,ans,A,B,K,a,b,F; 5 set
         
          Ans; 6 vector
          
            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
           
            =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
            
              ::iterator it1 = lower_bound(Ans.begin(),Ans.end(),F);37         set
             
               ::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 }