51 Nod 1082 与7无关的数

女爷i 2022-05-15 03:57 165阅读 0赞

一个正整数，如果它能被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

直接打表也可以过，但是要注意的是数据溢出的问题，要么直接全部开long long ,要么就要注意数据的强制类型转换

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    ll a[1000000+10];
    ll solve(ll x)
    {
        if(x%7==0) return 1;
        int flag=0;
        while(x)
        {
            int t=x%10;
            if(t==7)
            {
                flag=1;
                break;
            }
            x/=10;
        }
        if(flag) return 1;
         return 0;
    }
    
    int main(){
    	ll n;
    	for(ll i=1;i<=1000000;i++){
    		if(!solve(i)){
    			a[i]=a[i-1]+i*i;
    		}
    		else{
    			a[i]=a[i-1];
    		}
    	}
    	scanf("%lld",&n);
    	for(ll i=0;i<n;i++){
    		ll x;
    		scanf("%lld",&x);
    		printf("%lld\n",a[x]);
    	}
    	return 0;
    }

二分加预处理。  
[链接][Link 1]  
虽然感觉这里不用二分，直接暴力更好，但是感觉加个二分代码更有灵气，哈哈

#include<iostream>
    #include<algorithm>
    using namespace std;
    long int add(long int first,long int last) {
    	if(first==last) {
    		if(first%7==0) return 0;
    		while(first!=0) {
    			long int n=first%10;
    			first=first/10;
    			if(n==7) return 0;
    		}
    		return last*last;
    	}
    	int mid=(first+last)/2;
    	return add(first,mid)+add(mid+1,last);
    }
    int main() {
    	
    	long  int i,j,t,m;
    	int a[1000];
    	int b[1000];
    	int c[1000];
    	cin>>t;
    	for(i=0; i<t; i++) {
    		cin>>a[i];
    		c[i]=a[i];
    	}
    	sort(c,c+t);
    	
    	for(i=0; i<t; i++)
    		if(a[i]==c[0]) break;
    	b[i]=add(1,c[0]);
    	m=i;
    	for(i=1; i<t; i++) {
    		for(j=0; j<t; j++)
    			if(a[j]==c[i]) break;
    		b[j]=b[m]+add(c[i-1]+1,c[i]);
    		m=j;
    	}
    	for(i=0; i<t; i++)
    		cout<<b[i]<<endl;
    	return 0;
    }

[Link 1]: https://www.51nod.com/user/index.html#!userId=24089