首页 > 代码库 > 51nod 1082 与7无关的数 （打表预处理）
51nod 1082 与7无关的数 （打表预处理）
1082 与7无关的数
题目来源： 有道难题
基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题
收藏
关注
取消关注一个正整数，如果它能被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
和素数筛法有点类似，打表预处理与7有关的数并求出前缀和。然后调用前缀和数组。
注意数据溢出。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 const int maxn=1e6+10; 5 int n; 6 bool valid[maxn]; 7 long long sum[maxn]; 8 void init() 9 { 10 memset(valid,true,sizeof(valid)); 11 //能被7整除 12 for(int i=7;i<maxn;i+=7) 13 valid[i]=false; 14 //数位上含7 15 for(int i=1;i<maxn;i*=10)//枚举个位、十位、百位... 16 { 17 int tmp=i*10; 18 for(int j=i*7;j<maxn;j+=tmp) 19 for(int k=0;k<i;k++) 20 { 21 valid[j+k]=false; 22 } 23 } 24 sum[0]=0; 25 for(long long i=1;i<maxn;i++)//递推求前缀和 26 { 27 if(valid[i]) 28 sum[i]=sum[i-1]+i*i; 29 else 30 sum[i]=sum[i-1]; 31 } 32 } 33 int main() 34 { 35 int t; 36 cin>>t; 37 init(); 38 while(t--) 39 { 40 cin>>n; 41 cout<<sum[n]<<endl; 42 } 43 return 0; 44 }
51nod 1082 与7无关的数 （打表预处理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。