2 暴力求解/数学问题

数学问题

素数

算术基本定理:若 $a\in Z$ , $a\gt 1$ ,则有 $a=p_1p_2\cdots p_n$ ,其中 $p_i$ 为素数

Proof:

假定定理对所有小于a的正整数均成立若a为素数,则结论显然成立若a为合数, $a=bc$ ,其中 $1\lt b,c\lt a$ 由归纳假设 $b=p_1p_2\cdots p_k,c=p_{k+1}p_{k+2}\cdots p_n$

找出素数
判断素数及分解质因数

for(int i = 2; i <= n; i++)
{
    if(!vis[i])
    prime[cnt++] = i;
    for(int j = 0; j<cnt && i*prime[j]<=n; j++)
    {
        vis[i*prime[j]] = 1;
        if(i % prime[j] == 0) break;
    }
}

易错点

1的特殊处理

bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ ) // 9
        if (x % i == 0)
            return false;
    return true;
}
bool divide_by_prime(int x){
    for(int i=2;i<=x/i;++i){
        int cnt = 0;
        while(x%i==0){
            x/= i;
            cnt ++;
        }
        if(cnt>0)printf("%d %d\n",i,cnt);
    }
    if(x>1)printf("%d 1\n",x);
}

gcd

Euclid's Algorithm(欧几里得算法) $lcm(m,n)=\frac{mn}{gcd(m,n)}$

long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}//原来a>b现调换

回文数

for(int i = 0; i < n / 2; i++) {//注意点1，是否改变中位数
    if(arr[i] != arr[n-1-i])//注意点2,n-1
    {         
        printf("No\n");            
        flag = 1;break;        
    }    
}if(!flag)printf("Yes\n");

str2num & num2str

int str2num(char *a)
{
    return 26 * 26 * (a[0]-'A') + 26 * (a[1]-'A') + (a[2]-'A');
}
string num2str(int num){
    string a(3,0);
    a[0] = num / (26 * 26)+'A';
    a[1] = num / 26 % 26 + 'A';
    a[2] = num % 26 + 'A';
    return a;
}

高精度

加法减法乘法: Input and Output Little Endian
乘法: 大Input Little Endian 小Input正常存结果Little Endian
除法: Big Endian

string addBig(string A, string B){
    int m = A.size(), n = B.size();
    int carry = 0;
    string C;
    if(m<n)return addBig(B,A);
    for(int i = 0;i<m;++i){
        carry += A[i]-'0';
        if(i<n)carry += B[i]-'0'
        C += (t%10 + '0');
        carry = carry/10;
    }
    if(carry) C += (t+'0');
    return C;
}
// negative
// (1) m < n 
// (2) m == n && 存在(A[j]= B[j](j<i) but A[i]< B[i])
// if(negative) minusBig(B,A)
string minusBig(string A, string B){
    int m = A.size(), n =B.size();
    int carry = 0;
    string C;
    for(int i =0;i<m;++i){
        carry+= A[i]-'0';
        if(i<n) carry -= (B[i]-'0');
        C += (carry+10)%10 + '0'; // carry的处理
        carry = carry>=0?0:-1;
    }
    while(C.size()>1&&C.back()=='0')C.pop_back();
    return C;
}
string multiplyBig(string A, string B){
    int b = stoi(B);
    int m = A.size();
    int t =0;
    string C;
    for(int i=0;i<m||t;++i){
        if(i<m)t += b*(A[i]-'0');
        C += (t%10 +'0');
        t/= 10;
    }
    while(C.size()>1&&C.back()=='0')C.pop_back();
    return C;
}
void divideBig(string A,string B){
    int t = 0;
    int b = stoi(B);
    int m = A.size();
    for(int i = 0;i< m;++i){
        t = t*10 + A[i] - '0';
        C += t/b +'0';
        t %= b;
    }
    int i = 0;
    for(i =0;i<C.size()-1;++i)if(C[i]!='0')break;
    cout<<C.substr(i)<<endl;
    cout<<t<<endl;
}

求解技巧

思路:遍历范围内全部数字,依据首+尾/首+间隔遍历

1.字符串特性

PAT题，利用次序

for (int i = 0; i < len; i++) {
    if (s[i] == 'T')countt++;
}
for (int i = 0; i < len; i++) {
    if (s[i] == 'P')countp++;
    if (s[i] == 'T')countt--;
    if (s[i] == 'A')result = (result + (countp * countt) % 1000000007) % 1000000007;
}

数学形式题注意对数字的直接利用，少用字符串特性

2.数组特性

不连续:利用基数和
Leetcode1711 Count Good Meals
题目
A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.
Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the ith item of food, return the number of different good meals you can make from this list modulo $10^9 + 7$ .
$1 <= deliciousness.length <= 10^5$
$0 <= deliciousness[i] <= 2^{20}$
int countPairs(vector<int>& deliciousness) { unordered_map<int,int> m; int res=0; for(int &p:deliciousness){ for(int i=1;i<=pow(2,21);i<<=1){ if(m.count(i-p)){ res=(res+m[i-p])%1000000007; } } m[p]++; } return res; }
Leetcode1846 Maximum Element After Decreasing and Rearranging
题目
You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:
The value of the first element in arr must be 1. The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, $abs(arr[i] - arr[i - 1]) <= 1$ for each i where $1 <= i < arr.length$ . There are 2 types of operations that you can perform any number of times:
Decrease the value of any element of arr to a smaller positive integer. Rearrange the elements of arr to be in any order. Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.
class Solution { public: int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) { fill(cnt,cnt+100001,0); int n=arr.size(); int miss=0; for(int i=0;i<n;++i)cnt[min(arr[i],n)]++; for(int i=1;i<=n;++i){ if(cnt[i]==0)miss++; else{ miss-=min(miss,cnt[i]-1); } } return n-miss; } private: int cnt[100001]; };

连续:利用前缀和/差分

//一维前缀和
S[i] - S[j-1]// a[j] +...+a[i]
//一维差分
a[i+1] = S[i+1] - S[i]// S[i]: 到i为止的和
/* 应用:
    s[i]... s[j]同时+c
    => a[i]: +c, a[j+1]: -c
*/
//二维前缀和
S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1]//以(x1,y1)为左上角,(x2,y2)为左下角的矩形面积
//二维差分
S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]//S[i][j]: 以i,j结果与Two axies围成的矩形面积
/* 应用:
    以(x1,y1)为左上角,(x2,y2)为左下角的矩形同时+c
    => a[x1][y1]: +c, a[x1][y1+1]: -c
       a[x2+1][y1]: -c, a[x2+1][y2+1]:+c        
*/

Leetcode413 Arithmetic Slices

题目

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

int numberOfArithmeticSlices(vector<int>& nums){
    int n=nums.size();
    int dp=0;
    int sum=0;
    for(int i=2;i<n;++i){
        if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){
            sum+=++dp;
        }
        else dp=0;
    }
    return sum;
}

3.矩阵性质

Rotate String

Given a string(Given in the way of char array) and an offset, rotate the string by offset in place. (rotate from left to right).

Example

Input: str="abcdefg", offset = 10

Output: str = "efgabcd"

利用 $(A^TB^T)^T=BA$

void rotateString(string &str, int offset) {
    int n=str.size();
    if(n>0){
        offset%=n;
        reverse(str.begin(),str.begin()+n-offset);
        reverse(str.begin()+n-offset,str.end());
        reverse(str.begin(),str.end());
    }
}

2 暴力求解/数学问题

数学问题​

素数​

gcd​

回文数​

str2num & num2str​

高精度​

求解技巧​

数学问题

素数

gcd

回文数

str2num & num2str

高精度

求解技巧