题目描述：
给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。
样例输入
1 4
样例输出
4
2
1
1
0
0
0
0
0
数据范围
n,m<=10^9
心态崩了，这是lv神考试的Day5 T1
看上去是个大水题，直接模拟呗，结果一看数据范围，顿时懵逼
我们年级其他的同学基本上都很明智的弃了，只有我还在很傻的写题（怎么如此耳熟）
既然要写，就一定要有效果，所以在一番深思熟虑后，我决定写一个暴力
是的，就是一个暴力，很符合社会主义价值观的暴力，然后加了一点小小的优化
比如说，在求约数的时候，将上限定为sqrt(x)，然后就跑的fo快
然后又不由自主的开始打表，无奈数据实在太大，最后电脑卡了，我代码还没存
伤心到变形，然后发现暴力能拿五十分，就开心的不得鸟
估算了一下，打表的话大概是可以到10^8左右（要跑三个小时）
具体代码如下：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int l,r; int ans[106]; void solve(int x){ for(register int i=1;i<=sqrt(x);i++){ if(x%i!=0) continue; int set=0; int h=i; while(h){ set=h%10; h/=10; } ans[set]++; if(i*i!=x){ if(i>sqrt(x)) continue; h=x/i; while(h){ set=h%10; h/=10; } ans[set]++; } } return ; } int main(){ int l=rd(),r=rd(); for(register int i=l;i<=r;i++) solve(i); for(register int i=1;i<=9;i++){ write(ans[i]); puts(""); } return 0; }
然后考完了去学习正解，发现是个数论题（其实谁都知道是数论，但就是不会写QAQ）
我们不难发现，暴力是绝对会T的，所以在计算的时候不能每次加一，而是要每次加一个区间的值
所以转换思路，我们知道两个数啊，a,b的乘积在区间l到r之间的话，a和b就都是合法的，所以我们来枚举a这个数，之后再判断b是否与a重复就可以了
具体代码如下：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> using namespace std; inline long long rd(){ long long x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(long long x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } long long n,m; long long cnt[10]; long long gets(long long l,long long r,long long x){ long long sum=0; if(x<r) r=x;//确定边界 long long md=x%r; long long num=x/r;//num枚举的就是上文中的a while(1){ long long f=(r-md)/(num+1);//是上文的b if(f*(num+1)<r-md) f++; if(l+f>r) break;//超出边界 sum+=f*num; md=(num*f+md)%(r-f); r-=f; if(f==1) num=(x/r); else num++; } return sum+(r-l+1)*num; } void solve(long long x,long long y){//x表示右端点,y表示是加还是减 for(long long i=1;i<=9;i++){ long long set=1;//处理不同的数位的时候，枚举10^i while(1){ if(i*set>x) break;//保证要处理的数的数位足够多 cnt[i]+=y*gets(i*set,((i+1)*set)-1,x);//当前数位所有的数 set*=10;//10的次方 } } return ; } int main(){ n=rd(),m=rd(); solve(m,1);//处理的时候因为不好枚举从l到r，所以我们计算出从1分别到l-1和r,然后作差就可以了（很像数位dp） solve(n-1,-1); for(long long i=1;i<=9;i++){ write(cnt[i]); puts(""); } return 0; }