欧拉计划个人题解(021-025)

algorithm
Project Euler, algorithm
文章目录
  1. 1. [021]Amicable numbers
  2. 2. [022]Names scores
  3. 3. [023]Non-abundant sums
  4. 4. [024]Lexicographic permutations
  5. 5. [025]Lattice paths

[021]Amicable numbers

题意

在正整数数域内，有一个数x，他的所有因子之和（不包括自身），等于另一个数y（$y \neq x$）；同时，y的所有因子和（不包括自身），等于数x。则x和y称为亲和数对，x和y都属于亲和数。

现求1到10000内所有亲和数之和。

思路

对每个数进行整数乘法，统计到对应数的因子和，然后再进行线性扫描即可。

代码

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MAXN = 10000;
int num[MAXN + 1];
int main(void)
{
    memset(num,0,sizeof(num));
    for(int i = 1; i <= MAXN; ++i)
    {
        for(int j = i * 2; j <= MAXN; j += i)
            num[j] += i;
    }
    int ans = 0;
    for(int i = 1; i <= MAXN; ++i)
    {
        if(num[i] <= MAXN && num[ num[i] ] == i && num[i] != i) // "num[i] != i" is important
            ans += i;
    }
    cout << ans << endl;
    return 0;
}

答案

31626

[022]Names scores

题意

给一个只包含大写英文的名(first name)文件，根据他们的位置，计算他们的价值，他们的价值定义为：每一位字母的在字母表中的序号之和与该姓名在所有名中的位置之乘积。
现求他们的价值和。

思路

读取直接做，C++的格式化读入还是比较麻烦。

代码

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
string next(ifstream& in)
{
    vector<char> buffer;
    char tmp = -1;
    while(in >> tmp && tmp != '"');
    if(tmp == -1)
        return string(1,'\0');
    in >> tmp;
    do{
        buffer.emplace_back(tmp); // There would not read '"' into buffer.
        in >> tmp;
    }while(tmp != '"');
    string str(buffer.size(), '\0');
    auto viter = buffer.begin();
    auto siter = str.begin();
    while(viter != buffer.end() && siter != str.end())
        *siter++ = *viter++;
    return str;
}
int main()
{

    ifstream dataStreamer;
    dataStreamer.open("p022_names.txt", ios::in, _SH_DENYWR);
    if(!dataStreamer)
    {
            cout<<"文件读错误";
            system("pause");
            exit(1);
    }

    set<string> s;
    while(true)
    {
        string str = next(dataStreamer);
        if(str.size() == 1)
            break;
        s.insert(str);
    }
    dataStreamer.close();
    int ans = 0;
    {
        int cnt = 1;
        for(string e : s)
        {
            int tmp = 0;
            for(char c : e)
               tmp += c - 'A' + 1;
            ans += cnt * tmp;
            ++cnt;
        }
    }
    cout << ans << endl;
    return 0;
}

答案

871198282

[023]Non-abundant sums

题意

28的因数为1，2，4，7，14。1+2+4+7+14=28，称28为完美数。
已知n，其因数和sum大于n，称n为多余数。12是最小的多余数，24是最小得可以有两个多余数相加。超过28123的任何数都可以写成两个多余数相加。
那么找出所有的无法由两个多余数组成的正整数之和。

思路

先建一个数组确认有哪些是多余数，再建一个数组确认这些多余数可以组成什么数，注意一个数可以被两个同样的多余数相加得到。

代码

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int abundantNumberCheck[28123 + 1];
bool abundantNumberMixed[28123 + 1];
int main()
{
    memset(abundantNumberCheck, 0, sizeof(abundantNumberCheck));
    memset(abundantNumberMixed, 0, sizeof(abundantNumberMixed));
    vector<int> abunantNumber;
    for(int i = 2;i <= 28123; ++i)
    {
        for(int j = i * 2; j <= 28123; j += i)
            abundantNumberCheck[j] += i;
        if(abundantNumberCheck[i] > i)
            abunantNumber.push_back(i);
    }

    for(size_t v1 = 0; v1 < abunantNumber.size(); ++v1)
        for(size_t v2 = v1; v2 < abunantNumber.size(); ++v2)  // it means that a number can be expressed two same numbers
        {
            if(abunantNumber[v1] + abunantNumber[v2] > 28123)
                break;
            abundantNumberMixed[ abunantNumber[v1] + abunantNumber[v2] ] = true;
        }
    int sum = 0;
    for(int i = 1; i < 28123 + 1; ++i)
    {
        if(abundantNumberMixed[i] == false)
            sum += i;
    }
    cout << sum << endl;
    return 0;
}

答案

4179871

[024]Lexicographic permutations

题意

找0、1、2、3、4、5、6、7、8、9这些数组合成一个数进行字典序排序后第一百万个数。

思路

DFS，先确认第一个数，这样可以算出后面有多少种情况，若第一百万不在里面就要调整第一个数，依次推类直到最后一个数字。

代码

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int TARGET = 1e6;
const int RANGE = 10;
int getPro(int n)
{
    int ans = 1;
    for(int i = n; i > 1; --i)
        ans *= i;
    return ans;
}
list<int> num;
void dfs(int target, int p, queue<int> &s)
{
    if(p == 1)
    {
        s.push(*num.begin());
        return ;
    }
    int part = getPro(p-1);
    cout << "part" << part << endl;
    auto i = num.begin();
    for(;i != num.end(); ++i)
        if(target <= part)
        {
            cout << *i << "b" << endl;
            break;
        }
        else
            target -= part;
    s.push(*i);
    num.erase(i);
    dfs(target, p-1,s);
}

int main(void)
{
    queue<int> s;
    for(int i = 0; i < RANGE; ++i)
        num.push_back(i);
    dfs(TARGET, RANGE, s);
    long long ans = 0;
    while(!s.empty())
    {
        cout << s.front() << "xxx" << endl;
        ans = ans * 10 + s.front();
        s.pop();
    }
    cout << setfill('0') << setw(10) << ans << endl;
    return 0;
}

答案

2783915460

[025]Lattice paths

题意

斐波那契数列：

$$
F_1 = 1 \\
F_2 = 1 \\
F_3 = 2 \\
F_n = F_{n-1} + F_{n-2} \\
$$
先要你求x，$F_x$的数位数第一次超过1000。

思路

高精度直接求就行，用我之前的模版，此处略模版细节。

代码

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    BigInt f[] = {BigInt::One(), BigInt::One(), BigInt::One()};
    int cnt = 0;
    while(f[cnt % 3].size() < 1000)
    {
        f[cnt % 3] = f[(cnt+1) % 3] + f[(cnt+2) % 3];
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

优化

自我考虑的，尚未实现：

已知 $log_{10}x$ 可以求x这个数字在十进制下的位数，我们又已知斐波那契数列的通项公式 $f(x)$ ，则 $1000 < log_{10}f(x)$ ，此时的x就是所求答案，但是斐波那契的 $(1+\sqrt{5})^x - (1-\sqrt{5})^x$ 我无法化成一个数字，将x这个项数用log的公式换下来。

答案

4782