一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7,则称其为与7相关的数。求所有小于等于N的与7无关的正整数的平方和。例如:N = 8,<= 8与7无关的数包括:1 2 3 4 5 6 8,平方和为:155。Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 1000)
第2 - T + 1行:每行1个数N。(1 <= N <= 10^6)
Output
共T行,每行一个数,对应T个测试的计算结果。
Input示例
5
4
5
6
7
8
Output示例
30
55
91
91
155
打表预处理。
AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int MAXN=1e6+10;
5
6 bool k[MAXN];
7 long long sum[MAXN];
8
9 int t,n;
10
11 void init(){
12 memset(k,true,sizeof(k));
13 for(int i=7;i<MAXN;i+=7){
14 k[i]=false;
15 }
16 for(int i=1;i<MAXN;i*=10){
17 int temp=i*10;
18 for(int j=i*7;j<MAXN;j+=temp){
19 for(int b=0;b<i;b++){
20 k[j+b]=false;
21 }
22 }
23 }
24 sum[0]=0;
25 for(long long i=1;i<MAXN;i++){
26 if(k[i]){
27 sum[i]=sum[i-1]+i*i;
28 }
29 else{
30 sum[i]=sum[i-1];
31 }
32 }
33 }
34
35 int main(){
36 cin>>t;
37 init();
38 while(t--){
39 cin>>n;
40 cout<<sum[n]<<endl;
41 //cout<<sum[1]<<endl;
42 }
43 return 0;
44 }
原文链接: https://www.cnblogs.com/Kiven5197/p/8514874.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/269983
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!