#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

vector<int> c;
int f[5050][5050];
int main() {
    int n ; cin >> n ;
    for(int i = 0 , last = -1 ; i < n ; ++i) {
        int col ; cin >> col ;
        if(last != col) {
            c.push_back(col);
            last = col;
        }
    }

    n = c.size(); 

    for(int len = 2 ; len <= n ; ++ len ){
        for(int i = 0 ; i < n ; ++i) {
            int j = i + len - 1 ;
            if(j >= n) break; 
            auto & ff = f[i][j] ; 
            ff = min(f[i+1][j] , f[i][j-1]) + 1;
            if(c[i] == c[j]) ff = min(ff , f[i+1][j-1] + 1);
        }
    }

    cout << f[0][n-1] ;
}

#include<iostream>
#include<queue>
#include <cstring>
using namespace std;

char a[1010][1010];
bool vis[1010][1010];
int d[1010][1010];

void bfs(int x , int y , int n , int m){

    memset(d, 0x3f ,sizeof d);

    auto q = queue<pair<int,int>>{};
    q.push({x,y});
    int dis = 0 ;
    vis[x][y] =true;
    while(q.size()){
        int cnt = q.size();
        while(cnt--){
            auto [i , j] = q.front(); q.pop();
            d[i][j] = dis;
            for(auto & [dx , dy] : {pair{-1 , 0} , {1,0} , {0,1},{0,-1}}){
                int u = dx + i , v = j + dy;
                if(u >= 0 && u < n && v >= 0 && v < m 
                && a[u][v] != 'T' && !vis[u][v]){
                    q.emplace(u,v);
                    vis[u][v] = true;
                }
            }
        }
        ++dis;
    }
}

int main(){
    int n , m ; cin >> n >> m;
    int ex , ey ;
    int sx , sy ;
    for(int i = 0 ; i < n ; ++i) {
        cin >> a[i];
        for(int j = 0 ; j < m ; ++j){
            if(a[i][j] == 'S') sx = i , sy = j;
            else if(a[i][j] == 'E') ex = i , ey = j;
        }
    }

    bfs(ex , ey , n , m);
    int ans = 0 ;
    int dis = d[sx][sy];
    for(int i = 0 ; i < n ; ++i) {
        for(int j = 0 ; j < m ; ++j){
            if(a[i][j] > '0' && a[i][j] <= '9' && d[i][j] <= dis)
                ans += a[i][j] - '0';
        }
    }

    cout << ans ;
}

推反素数序列的单调 + 稀疏性 , 暴力枚举

#include<iostream>

using namespace std;

int primes[] = {0,2,3,5,7,11,13,17,19,23};
int st[10] = {30};
int n;

void dfs(int u , long long v , int cur_g ,  long long & ans , int & g ){
    if(v > n || v <= 0 || cur_g > 2000) return ;
    if(u == 10){
        if(cur_g > g) ans = v , g = cur_g;
        else if(cur_g == g) ans = min(ans , v) ;
        return ;
    }

    int c = 0 ;
    for(; c < st[u-1] && v <= n; ++c) v *= primes[u];
    st[u] = c;
    for(int i = 0 ; i <= c ; ++i) {
        dfs(u + 1 , v , cur_g * (st[u] + 1) , ans , g);
        --st[u];
        v /= primes[u];
    }
    st[u] = 0;
}

int main(){
    cin >> n;
    long long ans = 0;
    int g = 0;
    int cur_g = 1;
    dfs(1 , 1 , cur_g , ans , g);
    cout << ans ;
}

#include <iostream>

using namespace std;

int main(){
    int t; cin >> t;
    while(t--){
        int n ; cin >> n ; 
        int a[110];
        for(int i = 0 ; i < n ; ++i) cin >> a[i];
        int i = 0 ; 
        int ans = 0 ;
        while(i < n && a[i] == 0) ++ans , ++i;
        int zcnt = 0;
        for(;i < n ; ++i) {
            if(a[i] == 1 ) {
                if(zcnt > 1) ans += zcnt;
                zcnt= 0 ;
            }
            else ++zcnt;
        }
        ans += zcnt;
        cout << n - ans << endl;
    }
}

确定每一个质因子的指数取值范围即可.

#include <iostream>
#include <vector>
#include <cassert>
#include <numeric>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
constexpr int N = 4e4 + 10;

vector<int> primes{};
map<int,int> prime_cnts[4];
set<int> prime_set;
bool test[N];

void init(){
    primes.reserve(N / 5);
    for(long long i = 2; i < N ; ++i) {
        if(test[i]) continue ;
        primes.push_back(i);
        for(auto j = i * i ; j < N ; j += i ) test[j] = true;
    }
}

void factoring(int n , int j){
    for(int i : primes){
        if(i * i > n) break;
        int c = 0;
        while(n % i == 0) n /= i , ++c;
        if(c) prime_cnts[j][i] = c , prime_set.insert(i);
    }
    if(n > 1) {
        prime_set.insert(n);
        prime_cnts[j][n] = 1;
    } 
}

void reset(){
    for(auto & ps : prime_cnts) ps.clear();
    prime_set.clear();
}

int main(){
    int n ; cin >> n;
    init();
    while(n--){
        int a1 , a0 , b1 , b0 ; cin >> a0 >> a1 >> b0 >> b1;

        reset();

        factoring(a0 , 0);
        factoring(a1 , 1);
        factoring(b0 , 2);
        factoring(b1 , 3);

        auto get_count_in_p = [](int ca0 , int ca1 , int cb0 , int cb1){

            int left = 0 , right = numeric_limits<int>::max() - 1;
            // assert(ca0 >= ca1);
            if(ca0 == ca1) left = max(left , ca1);
            else left = max(left , ca1) , right= min(right , ca1);

            // assert(cb0 <= cb1) ;
            if(cb0 == cb1) right = min(right , cb1);
            else left = max(left , cb1) , right = min(right , cb1);

            return max(0 , right - left + 1);
        };

        int ans = 1;

        for(int p : prime_set){
            if(ans == 0) break;

            int ca0 = prime_cnts[0][p];
            int ca1 = prime_cnts[1][p];
            int cb0 = prime_cnts[2][p];
            int cb1 = prime_cnts[3][p];

            ans *= get_count_in_p(ca0 , ca1 , cb0 , cb1);
        }

        cout << ans << endl;
    }
}

阶乘分解变种

#include <iostream>
#include <vector>

using namespace std;
constexpr int N = 1e6 + 10 ;
constexpr int mod = 1e9 + 7;
vector<int> primes{};
bool test[N];
int cnts[N];

void init_primes(){
    primes.reserve(N / 5);
    for(long long i = 2 ; i < N ; ++i){
        if(test[i]) continue ;
        primes.push_back(i);
        for(auto j = i * i ; j < N ; j +=i ) test[j] = true;
    }
}

void count(int n){
    for(int i = 0 ; i < primes.size() ; ++i) {
        int p = primes[i];
        for(long long j = p ; j <= n; j *= p ){
            cnts[i] += (n / j ) * 2;
        }
    }
}

int main(){
    int n ; cin >> n ; 
    init_primes();
    count(n);
    long long ans = 1 ;
    for(int i = 0 ; i < primes.size() ;++i) {
        ans = (ans * (cnts[i] + 1)) % mod;
    } 
    cout << ans ;
}

#include <iostream>
#include <cstring>
using namespace std;
constexpr int N = 1e6 + 10;

int a[N / 5];
bool vis[N];
int cnt[N];
int ans[N];

int main(){
    int n ; cin >> n ;
    int maxv = 0;
    for(int i = 0 ; i < n ; ++i) cin >> a[i] , cnt[a[i]] ++ , maxv = max(maxv , a[i]);

    for(int i = 0 ; i < n ; ++i) {
        if(vis[a[i]]) continue ;
        for(int j = a[i] ; j <= maxv; j += a[i]){
            ans[j] += cnt[a[i]];
        }
        vis[a[i]] = true;
    }

    for(int i = 0; i < n ; ++i) cout << ans[a[i]] - 1<< "\n";

}

#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>

using namespace std;

constexpr int N = 1e6 + 10;

vector<int> primes{};
vector<int> p2{};
bool test[N];

void init_primes(){
    primes.reserve(20000);
    for(long long i = 2 ; i < 50000 ; ++i ) {
        if(test[i]) continue ;
        primes.push_back(i);
        for(long long j = i * i ; j < 50000; j += i)
            test[j] = true;
    }
}

int main(){

    init_primes();
    long long l , r ; 
    while(cin >> l >> r){
        memset(test, 0 , sizeof test);

        for(int i : primes){
            if(i > r) break;

            long long beg = (l / i) * i;
            if(beg < l) beg += i;
            if(beg == i) beg += i;

            for(long long j = beg ; j <= r ; j += i) {
                test[j - l] = true;
            }
        }


        int minv = N , maxv = 0 ;
        int mil , mir , mal , mar;
        if( l == 1) test[0] = true;
        for(int i = 0 , prev = -1; i <= r - l ; ++i){
            if(test[i]) continue ;
            if(prev >= 0) {
                if(i - prev < minv) mil = prev , mir = i , minv = i - prev;
                if(i - prev > maxv) mal = prev , mar = i , maxv = i - prev;
            }
            prev = i;
        }


        if(maxv)
            cout << mil + l << "," << mir + l << " are closest, " 
                << mal + l<<"," << mar + l << " are most distant." << endl;
        else 
            cout << "There are no adjacent primes." << endl;
    }


}

#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 1e6 + 10;

bool test[N];

int main(){
    int n ; cin >> n ;
    auto primes = vector<int>{} ; primes.reserve(n);

    for(long long i = 2 ; i <= n ; ++i) {
        if(test[i]) continue ;
        primes.push_back(i);    
        for(long long j = i * i ; j <= n ; j += i) {
            test[j] = true; 
        }
    }
    for(int i: primes) {
        int cnt = 0 ;
        for(long long j = i ; j <= n  ; j *= i){
            cnt += n / j ;
        }
        if(cnt) cout << i << " " << cnt << endl;
    }

}

#include <iostream>

using namespace std;

constexpr long long mod = 100003  ;

long long fpow (long long n , long long e){
    long long ans = 1;
    while(e){
        if(e & 1) ans *= n ;
        n *= n ;
        ans %= mod;
        n %= mod;
        e >>= 1;
    }
    return ans;
}

int main(){
    long long m , n ; cin >> m >> n ; 
    if(m == 1) {
        cout << 1 << endl;
        return 0;
    } 

    m %= mod ;
    auto ans = m * ((fpow(m , n - 1) + mod - fpow(m -1, n - 1))%mod);
    ans %= mod;
    cout << ans << endl;
}