[TIOJ] 1361. 零的法則

題目連結:http://tioj.infor.org/problems/1361

---

卡了超久....寫了支暴搜對答案也看不出個所以然，最後才發現原來沒保證$a \leq b$，所以要判一下...

回到正題，觀察一下後會發現對於$[1, x]$中出現的0的個數，考慮個位時就是看$\lfloor \frac{x}{10^1} \rfloor$，但考慮十位時則是$\lfloor \frac{x}{10^2} \rfloor \times 10$，稍微想一下就可以推出考慮第$i$位時就是看$\lfloor \frac{x}{10^i} \rfloor \times 10^{i-1}$，不過要稍微注意一下邊界，若是不足$10^{i-1}$時要修正回來。

所以對於$[l, r]$做法就是用算$[0, r]-[0, l-1]$

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

inline int getSum(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int l, r;
	while(cin>>l>>r){
		if(l>r) swap(l, r);
		cout<<getSum(r)-getSum(l-1)<<'\n';
	}
	return 0;
}

inline int getSum(int x){
	if(x<0) return 0;
	int r=1;
	for(lld i=10;i<=x;i*=10){
		r += (x/i) * (i/10);
		if((x%i)<(i/10)) r -= (i/10)-(x%i)-1;
	}
	return r;
}