1.和leetcode里面的Number of Digit One一样,统计0~n中,出现多少个1.
2.算法说明:
如3141592,在m(digitDivide)=100时,即要求计算百位上“1”的个数
其中a为31415,b为92,31415中出现了3142次“1”,因为每10个数里面出现1次“1”。而实际上,31415是3141500,所以把31415中1的个数再乘以m。如3141400~3141499中,前缀为31414的数出现了100次,所以需要乘以m(此时是100)。
时间限制
10 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.
Input Specification:
Each input file contains one test case which gives the positive N (<=230).
Output Specification:
For each test case, print the number of 1’s in one line.
Sample Input:
12
Sample Output:
5
AC代码:
#include <iostream> #include <stdio.h> #include <vector> #include <stack> #include <algorithm> #include <memory.h> #include <map> #include <set> #include "limits.h" using namespace std; int main(void) { long long n; cin>>n; long long ans = 0; for(long long digitDivide=1;digitDivide<=n;digitDivide*=10) { long long a = n / digitDivide; long long b = n%digitDivide; ans+=(a+8)/10*digitDivide+(a%10==1)*(b+1); } cout<<ans<<endl; return 0; }