INOI 2015 - 周期性弦乐

Question

问题：https://www.codechef.com/INOIPRAC/problems/INOI1502

这就是我想到的 -

• 有一个函数f（n），它找到n的因子
• 如果找到一个因子i，则调用f（i）
• 对于n的每个值，该函数还计算非周期性字符串的数量将等于2 ^ n - （每个函数调用返回的值）
• 返回非周期性字符串的数量并将此数字存储在数组中以防止

然后我只需调用函数f（n）modulo n来获得输出

它适用于较小的值，但不适用于较大的值

例如，当n = 35＆m = 99999989时

我的代码截至目前：

#include <iostream>
#include <cmath>
using namespace std;
int arr[150100];
int ans[150100];
int check(int n){
    if(arr[n]>0){
        return arr[n];
    }
    else if(n == 1){
        arr[n] = 2;
        return 2;
    }
   if(n==2){
       arr[n] = 2;
       return 2;
    }
    for(int i =1 ;i<(n/2) +1;i++){

        if(n%i == 0){
            ans[n] -= check(i);//2+
        }
    }

    arr[n] = ans[n];
    return ans[n];
}
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=150100;i++){
        arr[i] = 0;
        ans[i] = pow (2,i);
    }
    std::cout<<( check(n) )%m<<endl;
}

---

Full problem statement:

字符串是0s和1s的任何非空序列。字符串的例子是00，101，111000，1，0，01。字符串的长度是其中的符号数。例如，111000的长度为6.如果u和v是字符串，则uv是通过连接u和v获得的字符串。例如，如果u = 110和v = 0010，则uv = 1100010。

如果存在字符串v使得w = vn = vv···v（n次），对于某些n≥2，字符串w是周期性的。注意，在这种情况下，v的长度严格小于w的长度。例如，110110是周期性的，因为它对于v = 110是vv。

给定正整数N，找到长度为N且不是周期性的字符串数。以M模块报告答案。长度为2的非周期性字符串是10和01。长度为3的非周期性字符串是001，010，011，100，101和110。

Input format

一行，有两个以空格分隔的整数，N和M。

Answer 1

好吧，我将从你选择的内置类型开始，它不是你的例子的最佳选择：n = 35＆m = 99999989。通常int的大小是32位，因此它能够保持最大2 ^ 32。因此，对于您的示例，您应该选择能够保持最少35位的类型。

long long也不是很好的选择因为你使用modulo函数适用于整数，如果你想在大于int的类型上应用modulo，你会更喜欢使用函数fmod，请参阅http://www.cplusplus.com/reference/cmath/fmod/。

在你的实现中我更喜欢使用double类型，在大多数系统上它的大小是64位，下面是带有一些更正的代码：

#include <iostream>
#include <cmath>
using namespace std;
double arr[150100];
double ans[150100];
double check(int n){
    if(arr[n]>0){
        return arr[n];
    }
    else if(n == 1){
        arr[n] = 2;
        return 2;
    }
    if(n==2){
       arr[n] = 2;
       return 2;
    }
    for(int i =1 ;i<(n/2) +1;i++){

        if(n%i == 0){
            ans[n] -= check(i);//2+
        }
    }

    arr[n] = ans[n];
    return ans[n];
}
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=0;i < 150100;i++){
        arr[i] = 0;
        ans[i] = pow(2.0,i);
    }
    std::cout<<static_cast<int>(fmod(check(n),m))<<endl;
}

请注意，此修复程序仅适用于N到64，因为在大多数系统中，双倍大小为64位。

您应该考虑的第二个问题是您的“ans”数组，您尝试使用比int大得多或双重能够容纳的值来初始化它，大于2 ^ 64的值。在这种情况下，“ans”中会有截断的数据。

对于这个任务，我更喜欢另一种方法，包括模幂运算规则：ab mod m =（a mod m）（b mod m）mod m =（a（b mod m））mod m

根据问题2中的描述≤M≤10^ 8，因此在此任务中保持整数数组就足够了。例如，要计算2 ^ 150000 mod 10 ^ 8，而不是直接评估2 ^ 150000，请逐步执行并在每一步采用模数。