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]]);
        }
    }