Description

一个侦探来到罪犯的据点，发现了一个密码锁。密码锁旁写着几行字：此锁的密码会不断变化，每次要输入时，密码锁会随机给出六个数s,t,a,b,c,d（1<=s<=t<=500,1<=a,b,c,d<=10000)。在第s个斐波那契数到第t个斐波那契数之间（包括第s个和第t个）所有不能被a，b，c，d任一数整除的斐波那契数所组成的数列就是密码。

斐波那契数(Fibonacci数)是组合数学中非常重要的一个数列，它的递推公式是：

F(1)=0，F(2)=1

F(n)=F(n-1)+F(n-2)

请你编一个程序，读入s,t,a,b,c,d六个数，然后求出密码锁的密码。

Input Format

输入文件password.in中，第一行有s，t（1<=s<=t<=500)两个数，第二行有a,b,c,d(1<=a,b,c,d<=10000)四个数。

Output Format

输出文件password.out中，依次输出组成密码的每个斐波那契数（相邻的数用空格隔开）。

1 5
2 3 5 7

1 1

Hint

当数字很大时，直接进行模运算可能会导致溢出，因此需要采用其他方法。下面介绍一种基于字符串的方法：

假设我们要判断一个大数 num 能否被 n 整除，将 num 转化为字符串，然后逐位计算其模 n 的值，最终得到 num 对 n 取模的结果。具体算法如下：

定义一个变量 rem 表示余数，初值为 0。
从 num 的最高位开始逐位计算：
将 rem 乘 10，再加上当前位上的数字，得到一个新的数 newNum。
将 newNum 对 n 取模，得到新的余数 newRem。
将 rem 的值更新为 newRem。
最终 rem 的值即为 num 对 n 取模的结果。
如果 rem 的值为 0，则 num 能被 n 整除，否则不能被整除。

下面是 C++ 的代码实现，可以处理大数的情况：

#include <iostream>
#include <string>
using namespace std;

bool divisible(string num, int n) {
    int rem = 0;
    for (int i = 0; i < num.size(); i++) {
        rem = rem * 10 + (num[i] - '0');
        rem %= n;
    }
    return rem == 0;
}

int main() {
    string num = "1234567890123456789012345678901234567890";  // 示例数字
    int n = 23;  // 示例模数
    if (divisible(num, n)) {
        cout << num << " is divisible by " << n << endl;
    } else {
        cout << num << " is not divisible by " << n << endl;
    }
    return 0;
}

值得注意的是，如果 num 可以被 long long 类型存储，直接对其取模可能更加高效。这种方法可以在模数很小（例如小于 1e9）的情况下使用。如果模数很大，字符串方法是一种更好的选择。

Source

高精度