指数+1的做法好像TLE
查看原帖
指数+1的做法好像TLE
524790
GeorgePeng楼主2022/8/31 21:37

rt.

//新方法:指数加1连乘方法
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
bool Isprime(int n) {
    for(int i = 2; i * i <= n; i++) if(n % i == 0) return true;
    return false;
}
int f(int n) {
    long long res = 1;
    if(n == 0 || n == 1) {
        return 1;
    }
    for(int i = 2; i <= n; i++) {
        if(Isprime(i)) continue;//如果它是合数,那就不行(为了节省时间复杂度)
        long long cnt = 0;
        while(n % i == 0) {
            cnt++;
            n /= i;
        }
        res *= (cnt + 1);
    }
    return res;
}
int main() {
	ll ans = 0;
	ll n; cin >> n;
	for(int i = 1; i <= n; i++) {
		ans += f(i);
//		cout << f(i) << ' ';
	}
//	cout << endl;
	cout << ans;
	return 0;
}

能不能帮助优化一下?

2022/8/31 21:37
加载中...