51nod--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

---

解题思路

---

/* 题目本身思路很简单，但是由于这里的数据量太大， 所以需要额外的一个思想，就是打表。 步骤如下：首先找到输入多组数据中的最大值max， 然后对这个最大值max进行题目意思求解，将1–max 中的每个求得的结果用一个数组记录下来， 完毕之后，直接输出即可。应为最大值都求出来了， 其他值坑定也求出来了、 */

---

代码

---

import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int T = sc.nextInt(); //int n = 0; int[] a = new int[T]; // 记录输入数据 int max = Integer.MIN_VALUE; for(int i=0; i<T; ++i){ a[i] = sc.nextInt(); if(max < a[i]) max = a[i]; } //注意这里的数据类型 long[] map = new long[max+1]; //inout //init long sum = 0; boolean flag = true; int tem = 0; //process for(int i=1; i<=max; ++i){ flag = true; tem = i; if(i % 7 == 0){ map[i] = map[i-1]; continue; } //分解数 while(tem != 0){ if((tem % 10) == 7){ flag = false; map[i] = map[i-1]; break; } tem /= 10; } //puanduan if(!flag) continue; //cal sum +=(long)i*i; // 这里一定要要 //转成long型，i*i可能会溢出 map[i] = sum; } //output for(int i=0; i<T; ++i) System.out.println(map[a[i]]); } }