首页 > 试题广场 >

被 7 整除

[编程题]被 7 整除

热度指数：1069 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小萌非常喜欢能被 7 整除的数字，比如 7,21,121996 ，等等。有一天他得到了 n 个正整数，她想用这些数制造出更多的能够被7整除的数。于是她从这 n 个数中选出两个数，然后将一个数写在另一个数的前面，以此得到一个新的数。按这种方法她一共可以得到

个数，她想知道在这些数中，有多少个是能被 7 整除的。

数据范围： $2 \le n \le 10^5 \$ ， $1 \le a_i \le 10^9 \$

输入描述:

第一行包含一个整数n。

第二行包含n个正整数a_i。

输出描述:

输出对应的答案。

示例1

输入

3
127 1996 12

输出

说明

一共有4种组合方式，其中：把12写在1996前面得到121996；把127写在12前面得到12712；把1996写在12前面得到199612；把1996写在127前面得到1996127；都是可以被7整除的，其余的组合方式不能被7整除。

算法知识视频讲解

嘟嘟6668

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while (scan.hasNext()) {
            int k=scan.nextInt();
            int[]data=new int[k];
            for(int i=0;i<k;i++){
                data[i]=scan.nextInt();
            }
            get(k,data);
        }
    }
    public static void get(int k,int[]data){
        int[][]tem=new int[7][10];
        for(int i=0;i<k;i++){
            int yu=data[i]%7;
            int len=(data[i]+"").length();
            tem[yu][len]++;
        }
        Mycon[]last=new Mycon[70];
        int count=0;
        for(int i=0;i<7;i++){
            for(int j=0;j<10;j++){
                if(tem[i][j]!=0){
                    Mycon h=new Mycon();
                    h.yu=i;
                    h.len=j;
                    h.num=tem[i][j];
                    last[count++]=h;
                }
            }
        }
        int finalans=0;
        for(int i=0;i<count;i++){
            for(int j=0;j<count;j++){
                if(i!=j){
                    int tog=1;
                    for(int m=0;m<last[j].len;m++){
                        tog*=10;
                    }
                    tog=tog*last[i].yu+last[j].yu;

                    if(tog%7==0){
                        finalans+=last[i].num*last[j].num;
                    }
                }else{
                    int tog=1;
                    for(int m=0;m<last[j].len;m++){
                        tog*=10;
                    }
                    tog=tog*last[i].yu+last[j].yu;
                    if(tog%7==0){
                        finalans+=last[i].num*(last[j].num-1);
                    }
                }
            }
        }
        System.out.println(finalans);
    }
}
class Mycon{
    int yu;
    int len;
    int num;
}

发表于 2019-06-04 21:06:26 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int F(int x){
    int cnt = 0;
    while(x){
        x /= 10;
        cnt++;
    }
    return cnt;
}

int main(){
    int n;
    scanf("%d", &n);
    int a[n], b[11][7]={0};
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        b[F(a[i])][a[i]%7]++;
    }
    long s = 0;
    for(int i=0;i<n;i++){
        int x=F(a[i]), y=a[i]%7;
        b[x][y]--;
        long t = a[i];
        for(int j=1;j<=10;j++){
            t *= 10;
            s += b[j][(7-t%7)%7];
        }
        b[x][y]++;
    }
    printf("%ld\n", s);
    return 0;
}

发表于 2020-09-18 08:33:12 回复(1)

卖报人

//我们可以把数按照其余数、位数（因为对于不被7整除的数，按照10^6倍数循环
//所以只需要有1+6*6个分组就好了
//接下来我们只需要找到对应分组的组合（一种余数+位数的数作为结尾时，拼在他前面的应该的余数是多少
//如果找到拼在其前面的余数要求和该类数一致，证明是同组排列，N*(N-1)
//否则就是不同组的排列：N*M
//都加一起就行了

#include<iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int mylist[6] = {1,3,2,6,4,5};
    int rec[7][6] = {0};
    int recsum[7] = {0};
    long long tmp;
    int pos1, pos2, posrec;
    long long res;
    for(int i = 0; i < n; i++) {
        cin>>tmp;
        pos1 = tmp%7;
        pos2 = 0;
        if(pos1 != 0) {
            while(tmp > 0) {
                tmp = tmp/10;
                pos2++;
            }
        }
        pos2 = pos2%6;
        rec[pos1][pos2]++;
    }
    
    for(int i = 1; i < 7; i++) {
        for(int j = 0 ; j < 6; j++) {
            recsum[i] = recsum[i] + rec[i][j];
        }
    }
    
    res = rec[0][0]*(rec[0][0]-1);
    
    for(int i = 1; i < 7; i++) {
        for(int k = 0; k < 6; k++) {
            if(mylist[k] + i == 7) {
                posrec = k;
                break;
            }
        }
        for(int j = 0 ; j < 6; j++) {
            pos1 = posrec - j;
            if(pos1 < 0) {
                pos1 = pos1 + 6;
            }
            if(i == mylist[pos1]) {
                res = res + rec[i][j]*(recsum[mylist[pos1]]-1);
            }
            else{
                res = res + rec[i][j]*recsum[mylist[pos1]];
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2020-07-12 16:47:54 回复(0)

chorifa

// [prefix 0~6][suffix 0~6][digcnt 1~9]情况是有限的
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] remDigCnt = new int[7][10];
        int[] remCnt = new int[7];
        int[] offset = {1,10%7,100%7,1000%7,10000%7,100000%7,1000000%7,10000000%7,100000000%7,1000000000%7};
        String[] strs = br.readLine().split(" ");
        br.close();
        for(int i = 0; i < n; i++){
            int tmp = Integer.parseInt(strs[i]);
            int r = tmp%7, bitcnt = 0;
            for(;tmp != 0; tmp /= 10) bitcnt++;
            remDigCnt[r][bitcnt]++;
            remCnt[r]++;
        }
        int res = 0;
        for(int prefix = 0; prefix < 7; prefix++)
            for(int suffix = 0; suffix < 7; suffix++)
                for(int digcnt = 1; digcnt < 10; digcnt++)
                    if((offset[digcnt]*prefix+suffix)%7 == 0)
                        res += (prefix==suffix?(remCnt[prefix]-1):remCnt[prefix])*remDigCnt[suffix][digcnt];
        System.out.println(res);
    }
}

发表于 2019-05-08 21:22:25 回复(0)

Java

牛客35031561号

被7整除的数

暴力做法时间复杂度O(NN), 2 <= n <= $10^5$ ,会超时。

暴力做法：枚举第一个数x, 再枚举第二个数y,拼接两个数， bit(y) 表示y是几位数。

因此，得到的新数是： $x \times 10^{bit(y)}+y$ ，
我们在暴力算法基础上优化算法。
我们又知道，A % 7 = a, B % 7 = b，如果(a+b) % 7 == 0，则一定有 $A \times 10^{bit(B)} + B$ % 7 等于0。

为了降低复杂度我们可以先预处理出来所有数是几位数，% 7 余几。每位数都是1位数到10位数，因此可以直接从表中查出当前数和1-10位数拼接，并且想要拼接的这个数%7 余几。

import java.util.*;
public class Main {
    static int getBit(int t) { // 计算该为数字为几位数
        int cnt = 0;
        while(t > 0) {cnt++; t /= 10;}
        return cnt;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[][] bit = new int[11][7]; //计数,【x是几位数】【x mod 7】
        for(int i=0; i < n; i++) {
            a[i] = sc.nextInt();
            bit[getBit(a[i])][a[i] % 7]++; 
        }
        long res = 0L; 
        for(int i=0; i < n; i++) {
            int x = a[i] % 7, y = getBit(a[i]);
            bit[y][x] --; // 当前数先刨除在外
            long num = (long)a[i];
            for(int j=1; j <= 10; j++) {
                num = num * 10;
                int re = (int)(num % 7); // A mod 7 的余数
                res = res + bit[j][(7 - re) % 7]; //直接查找
            }
            bit[y][x] ++; // 恢复
        }
        System.out.println(res);
    }
}

编辑于 2020-06-24 21:33:37 回复(0)