P1590 失踪的7

时间限制 1.00s 内存限制 125.00MB

题目描述

远古的Pascal人也使用阿拉伯数字来进行计数，但是他们又不喜欢使用7，因为他们认为7是一个不吉祥的数字，所以Pascal数字8其实表示的是自然数中的7，18表示的是自然数中的16。下面计算一下，在正整数n范围以内包含有多少个Pascal数字。

输入格式

第一行为正整数t，接下来t行，每行一个正整数n(≤2^32-1)。

输入的是Pascal数字

t≤10000

输出格式

对于每个正整数n，输出n以内的Pascal数的个数。

输入输出样例 输入 #1

2 10 20

输出 #2

9 18

处理思路： 逆向思维（亦可正）：找出n内Pascal数字，考虑不含7个数。 100 内Pascal数，两位0~9数字进行排列，题意n为正整数，00无意义，可用来代表100。所以100的贡献值为1∗9²。 例子：4321 个位1贡献值，1∗9⁰ 十位2贡献值，2∗9¹ 百位3贡献值，3∗9² 千位4贡献值，4∗9³ 数位大于7时按特殊情况考虑，即减去一个数位的贡献值。 此外： n的取值范围（1<=n<=2³²-1),int范围是（-2³¹,2³¹-1)(四字节），正整数范围不够，变量类型定义为longlong，（-2⁶³,2⁶³-1)(八字节)。

#include<bits/stdc++.h> using namespace std; typedef long long LL; int main(){ int t; LL n, ans, atr; scanf("%d", &t); while(t--) { for (ans = 0, atr = 1, scanf("%lld", &n); n; n /= 10, atr *= 9) ans += atr*(n%10) - (n%10 >= 7 ? atr : 0); printf("%lld\n", ans); } return 0; }