一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7,则称其为与7相关的数。求所有小于等于N的与7无关的正整数的平方和。
例如:N = 8,<= 8与7无关的数包括:1 2 3 4 5 6 8,平方和为:155。
输入
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 1000) 第2 - T + 1行:每行1个数N。(1 <= N <= 10^6)
输出
共T行,每行一个数,对应T个测试的计算结果。
输入样例
5
4
5
6
7
8
输出样例
30 55 91 91 155
打表前缀和,然后直接输出。
代码:
#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int t,n; ll is[1000001]; ll check(ll d) { ll dd = d; if(d % 7 == 0) return 0; while(d) { if(d % 10 == 7) return 0; d /= 10; } return dd * dd; } int main() { for(int i = 1;i <= 1000000;i ++) { is[i] = is[i - 1] + check(i); } scanf("%d",&t); while(t --) { scanf("%d",&n); printf("%lld ",is[n]); } }