ProjectEuler 001 - 010

可以回顾的题目:

• 004
• 007
• 009

001

思路

计数问题，一步到位，否则超时

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;

ll f(int x, int y){
    int k = x / y;
    return  (ll)k * (k + 1) / 2 * y;
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        ll res = 0;
        res += f(n - 1, 3);
        res += f(n - 1, 5);
        res -= f(n - 1, 15);
        cout << res << endl;
    }
    return 0;
}

002

思路

略

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;

ll f(long n){
    ll res = 0;
    long pre = 1, now = 1, next;
    while(now < n){
        if(now % 2 == 0) res += now;
        next = pre + now;
        pre = now;
        now = next;
    }
    return res;
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long n;
        cin >> n;
        cout << f(n) << endl;
    }
    return 0;
}

003

思路

略

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        long n;
        cin >> n;
        long mx = 0;
        for(long i = 2; i <= n / i; i++){
            while(n % i == 0){
                n /= i;
                mx = max(mx, i);
            }
        }
        if(n > 1) mx = max(mx, n);
        cout << mx << endl;
    }
    return 0;
}

004

思路

算有点小技巧吧，巧用upper_bound函数

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<int> s;

bool cmp(const int &a, const int & b){
    return a > b;
}

bool check(int n){
    int res = 0;
    int t = n;
    while(t){
        res = res * 10 + t % 10;
        t /= 10;
    }
    return res == n;
}

void init(){
    for(int i = 100; i <= 999; i++){
        for(int j = i; j <= 999; j++){
            int k = i * j;
            if(check(k)) s.push_back(k);
        }
    }
}

int main(){
    int t;
    cin >> t;
    init();
    sort(s.begin(), s.end(), cmp);
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        cout << *upper_bound(s.begin(), s.end(), n, cmp) <<endl;
    }
    return 0;
}

005

思路

略

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b){
    return (ll)a * b / gcd(a, b);
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        int res = 1;
        for(int i = 1; i <= n; i++) res = lcm(res, i);
        cout << res << endl;
    }
    return 0;
}

006

思路

求一下通项公式

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        cout << (ll)(n - 1) * n * (n + 1) / 6 * (3 * n + 2) / 2 << endl;
    }
    return 0;
}

007

思路

线性筛，有趣的bug

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 120000;
int a[N];
bool st[N];
int cnt;

void init(){
    for(int i = 2; i <= N; i++){
        //if(cnt > 10000) break;
        if(!st[i]){
            a[cnt++] = i;
        }
        for(int j = 0; a[j] <= N / i; j++){
            st[a[j] * i] = true;
            if(i % a[j] == 0) break;
        }
    }
}

int main(){
    init();
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        cout << a[n - 1] << endl;
    }
    return 0;
}

008

思路

略

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        int k;
        cin >> n >> k;
        string num;
        cin >> num;
        vector<int> a;
        for(auto c : num) a.push_back(c - '0');
        int res = 1;
        for(int i = 0; i < k; i++){
            res *= a[i];
        }
        for(int i = k; i < n; i++){
            int t = 1;
            for(int j = 0; j < k; j++) t *= a[i - j];
            res = max(res, t);
        }
        cout << res << endl;
    }
    return 0;
}

009

思路

一点小技巧吧，若成立则有:

$$\begin{aligned} a + b + c &= n\\ a^2 + b^2 &= c^2\\ a^2 + b^2 &= (n - a - b)^2\\ a^2 + b^2 &= n^2 + a^2 + b^2 + 2ab - 2n(a + b)\\ 0 &= n^2 + 2ab - 2na - 2nb\\ b &= (n^2 - 2na)/ (2a - 2n) \\ b & = (a ^ 2 - (a - n)^2) / 2(n - a) \end{aligned}$$

即有：

$$b = \frac{a ^ 2 - (a - n)^2}{2(n - a}$$

于是，所以，易得。

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int f(int n){
    if(n & 1) return -1;
    int res = -1;
    for(int a = n / 3; a >= 1; a--){
        int b = (a * a - (a - n) * (a - n)) / 2 / (a - n);
        int c = n - a - b;
        if(a >= b || b >= c) continue;
        if(a * a + b * b == c * c){
            res = max(res, a * b * c);
        }
    }
    return res;
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        cout << f(n) << endl;
    }
    return 0;
}

010

思路

基本就是线性筛法

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
int primes[N];
ll s[N];
bool st[N];
int cnt;

void init(){
    for(int i = 2; i <= N; i++){
        if(!st[i]){
            primes[cnt++] = i;
        }
        for(int j = 0; primes[j] <= N / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
        s[i] = s[i - 1] + i * (1 - st[i]);
    }
}


int main(){
    init();
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        cout << s[n] << endl;
    }
    return 0;
}