高精度除法，LeetCode2575. 找出字符串的可整除数组

目录

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div  是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0

返回 word 的可整除数组。

2、接口描述

​

class Solution {
public:
    vector<int> divisibilityArray(string a, int m) {

    }
};

3、原题链接

2575. 找出字符串的可整除数组

二、解题报告

1、思路分析

高精度除法板子题，详见高精度运算合集，加减乘除，快速幂，详细代码，OJ链接-CSDN博客

2、复杂度

时间复杂度： O(N)空间复杂度：O(1)

3、代码详解

​

class Solution {
public:
    vector<int> divisibilityArray(string a, int m) {
        vector<int> ret;
        for(long long i = 0, n = a.size(), s = 0; i < n; i++)
            s = (s << 1) + (s << 3) + (a[i] ^ 48), ret.emplace_back((s % m) == 0), s %= m;
        return ret;
    }
};