10175101159 edited 5 年前
本弱鸡还不会数位DP，于是使用了一些数学技巧进行正面实现（懒得写思路了，大概是排列组合）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string a,b;
ll mpow(ll a,ll b)
{
ll ret = 1;
while(b--){
ret *= a;
}
return ret;
}
ll mix(string s)
{
ll temp = 0;
for(int i = s.length() - 2;i >= 0;--i){
temp += s[i] - '0';
}
ll ret = temp % 9;
return ret ? 9 - ret : 0;
}
ll cal(string s)
{
ll len = s.length();
ll ret = 0;
for(ll i = 0;i < len - 1;++i){
if(s[i] == '9'){
for(ll j = i;j < len;++j){
s[j] = '8';
}
}
ret += (s[i] - '0') * mpow(9LL,len - i - 2) * 8LL;
}
ll left = min(s[len - 1],'8') - '0';
ret += left + 1;
if(mix(s) <= left)--ret;
return ret;
}
int main()
{
while(cin>>a>>b){
cout<<cal(b) - cal(a) + 1<<endl;
}
return 0;
}
这题还可以放宽条件，不要求输入的$a,b$都是妙数，代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
string change(ll x)
{
if(x == 0)return "0";
string ret = "";
while(x){
ret = (char)(x % 10 + '0') + ret;
x /= 10;
}
return ret;
}
ll mpow(ll a,ll b)
{
ll ret = 1;
while(b--){
ret *= a;
}
return ret;
}
ll mix(string s)
{
ll temp = 0;
for(int i = s.length() - 2;i >= 0;--i){
temp += s[i] - '0';
}
ll ret = temp % 9;
return ret ? 9 - ret : 0;
}
ll cal(string s)
{
ll len = s.length();
ll ret = 0;
for(ll i = 0;i < len - 1;++i){
if(s[i] == '9'){
for(ll j = i;j < len;++j){
s[j] = '8';
}
}
ret += (s[i] - '0') * mpow(9LL,len - i - 2) * 8LL;
}
ll left = min(s[len - 1],'8') - '0';
ret += left + 1;
if(mix(s) <= left)--ret;
return ret;
}
int main()
{
while(cin>>a>>b){
cout<<cal(change(b)) - cal(change(a - 1))<<endl;
}
return 0;
}