51nod1082 与7无关的数(打表)

2017年07月02日 12点热度 0人点赞 0条评论
题目来源: 有道难题
基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题

51nod1082 与7无关的数(打表) 收藏

51nod1082 与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

#include
#include
#include
using namespace std;
long long f[1000000+10]={0,1};
int main(){
	ios::sync_with_stdio(0);
	char s[10];
	for(int i=2;i<1000001;i++)
	{
		if(i%7==0)
		{
			f[i]=f[i-1];
			continue;
		}
		int flag=1;
		int t=i;
		while(t>0)
		{
			if(t%10==7)
			{
				flag=0;
				break;
			}
			t/=10;
		}
		if(flag) f[i]=f[i-1]+(long long)i*i;
		else f[i]=f[i-1];
	}
	int T,n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		cout<
未经允许不得转载!51nod1082 与7无关的数(打表)

update

纸上得来终觉浅, 绝知此事须躬行。