与7无关的数

2018/03/06 16:04
阅读数 7
一个正整数,如果它能被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 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部