解题思路

设输入的整数为 $n$（同时也是数组长度），我们要统计长度为 $n$ 的正整数数组 $a_1,\dots,a_n$，满足 $\forall\,1\le i\le n-1:\ \mathrm{lcm}(a_i,a_{i+1})=n$。

1）将问题转化到因子与质因数分解

若 $\mathrm{lcm}(x,y)=n$，必然有 $x|n,\ y|n$。将 $n$ 的质因数分解写作

$$n=\prod_{t=1}^k p_t^{e_t}.$$

把任意 $x|n$ 写作 $x=\prod p_t^{\alpha_t}$（其中 $0\le \alpha_t\le e_t$）。 条件 $\mathrm{lcm}(x,y)=n$ 等价于对每个素因子 $p_t$ 都有

$$\max(\alpha_t,\beta_t)=e_t.$$

因此 相邻两项的限制在每个素因子上完全独立：对每个 $p_t^{e_t}$，相邻两项在该素因子处的指数对 $(\alpha_t,\beta_t)$ 只需“至少有一个等于 $e_t$”。这意味着总答案可由乘法原理分解为各素因子上的计数乘积。

2）把每个素因子视作二元状态自动机

对固定的 $p^e$（省去下标），每个位置的指数可选 $0,1,\dots,e$ 共 $e+1$ 个值，但相邻限制只与“是否等于 $e$”有关。将状态压缩为两类：

• $E$：取值 $e$（只有 1 种选择）；
• $L$：取值 $0\sim e-1$（共有 $e$ 种选择）。

相邻不得出现 $L$ 紧跟 $L$（否则该素因子上的最大值达不到 $e$）。设长度为 $L$（此处 $L=n$）的序列计数为 $T_e(L)$。令

• $dp_E(i)$：长度为 $i$ 且以 $E$ 结尾的方案数；
• $dp_L(i)$：长度为 $i$ 且以 $L$ 结尾的方案数。

转移（对模 $M=10^9+7$）：

$$\begin{aligned} dp_E(i) &= dp_E(i-1)+dp_L(i-1),\\ dp_L(i) &= e\cdot dp_E(i-1), \end{aligned} \quad \text{初值 } dp_E(1)=1,\ dp_L(1)=e. $$

于是

$$T_e(i)=dp_E(i)+dp_L(i),\qquad \begin{bmatrix}dp_E(i)\\ dp_L(i)\end{bmatrix} = \underbrace{\begin{bmatrix}1&1\\ e&0\end{bmatrix}}_{A_e} \begin{bmatrix}dp_E(i-1)\\ dp_L(i-1)\end{bmatrix}. $$

所以

$$\begin{bmatrix}dp_E(L)\\ dp_L(L)\end{bmatrix} =A_e^{\,L-1}\begin{bmatrix}1\\ e\end{bmatrix},\qquad T_e(L)=dp_E(L)+dp_L(L). $$

这就是一个 2×2 矩阵快速幂 问题，时间 $O(\log L)$。

3）总体答案

设 $n=\prod p_t^{e_t}$，长度 $L=n$。各素因子独立，答案为

$$\text{Ans}=\prod_{t=1}^k T_{e_t}(L)\pmod{10^9+7}.$$

复杂度分析

• 设 $k$ 为 $n$ 的不同素因子个数（$k\le 60$），长度 $L=n$。
• 每个素因子做一次 2×2 矩阵快速幂：时间 $O(\log L)$；
• 整体时间复杂度 $O(k\log n)$，空间 $O(1)$（不计因式分解递归栈和常数级矩阵存储）。
• 对 $n\le 10^{18}$，结合 Pollard–Rho 的期望复杂度，可轻松在时限内通过。

代码实现

Python

import sys, random
sys.setrecursionlimit(10**7)

MOD = 10**9 + 7

# --- Miller-Rabin 判素（64位安全基集合） ---
def is_probable_prime(n: int) -> bool:
    if n < 2: return False
    small_primes = [2,3,5,7,11,13,17,19,23,29,31,37]
    for p in small_primes:
        if n % p == 0:
            return n == p
    # 写成 n-1 = d * 2^s
    d = n - 1
    s = (d & -d).bit_length() - 1  # 计算最低位1的位置-1，其实可循环除2
    while d % 2 == 0:
        d //= 2
    # 进行若干基的检测（上述 small_primes 亦可作为基集合）
    for a in [2,3,5,7,11,13,17,19,23,29,31,37]:
        if a % n == 0: 
            continue
        x = pow(a, d, n)
        if x == 1 or x == n-1: 
            continue
        ok = False
        for _ in range(s-1):
            x = (x * x) % n
            if x == n - 1:
                ok = True
                break
        if not ok:
            return False
    return True

# --- Pollard-Rho 因式分解 ---
def pollard_rho(n: int) -> int:
    if n % 2 == 0:
        return 2
    while True:
        c = random.randrange(1, n-1)
        f = lambda x: (x * x + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = gcd(abs(x - y), n)
        if d != n:
            return d

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

def factor(n: int, mp: dict):
    if n == 1:
        return
    if is_probable_prime(n):
        mp[n] = mp.get(n, 0) + 1
    else:
        d = pollard_rho(n)
        factor(d, mp)
        factor(n // d, mp)

# --- 2x2 矩阵运算（模 MOD） ---
def mat_mul(A, B):
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD, (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD, (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD],
    ]

def mat_pow(MAT, e):
    # 快速幂：返回 MAT^e
    R = [[1,0],[0,1]]
    A = [MAT[0][:], MAT[1][:]]
    while e > 0:
        if e & 1:
            R = mat_mul(R, A)
        A = mat_mul(A, A)
        e >>= 1
    return R

def count_for_exp(e: int, L: int) -> int:
    # 对固定指数 e，计算长度 L 的方案数 T_e(L)
    e_mod = e % MOD
    # 初始向量 v1 = [dpE(1), dpL(1)] = [1, e]
    if L == 1:
        return (1 + e_mod) % MOD
    A = [[1,1],[e_mod,0]]
    P = mat_pow(A, L-1)
    # vL = P * v1
    dpE = (P[0][0]*1 + P[0][1]*e_mod) % MOD
    dpL = (P[1][0]*1 + P[1][1]*e_mod) % MOD
    return (dpE + dpL) % MOD

def main():
    data = sys.stdin.read().strip().split()
    if not data: 
        return
    n = int(data[0])
    # 分解 n
    mp = {}
    factor(n, mp)
    # 计算乘积
    ans = 1
    for p, e in mp.items():
        ans = (ans * count_for_exp(e, n)) % MOD
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.math.*;

public class Main {

    static final long MOD = 1_000_000_007L;
    static final BigInteger BI_TWO = BigInteger.valueOf(2);

    // Miller-Rabin 通过 BigInteger 的 isProbablePrime
    static boolean isPrimeBig(BigInteger n) {
        // certainty 30 基本可视为确定
        return n.isProbablePrime(30);
    }

    static BigInteger rho(BigInteger n, Random rnd) {
        if (n.mod(BI_TWO).equals(BigInteger.ZERO)) return BI_TWO;
        while (true) {
            BigInteger c = new BigInteger(n.bitLength(), rnd);
            if (c.compareTo(BigInteger.ONE) <= 0 || c.compareTo(n.subtract(BigInteger.ONE)) >= 0) continue;
            BigInteger x = new BigInteger(n.bitLength(), rnd).mod(n);
            BigInteger y = x;
            BigInteger d = BigInteger.ONE;
            while (d.equals(BigInteger.ONE)) {
                x = x.multiply(x).add(c).mod(n);
                y = y.multiply(y).add(c).mod(n);
                y = y.multiply(y).add(c).mod(n);
                d = x.subtract(y).abs().gcd(n);
                if (d.equals(n)) break;
            }
            if (!d.equals(n)) return d;
        }
    }

    static void factor(BigInteger n, Map<BigInteger, Integer> mp, Random rnd) {
        if (n.equals(BigInteger.ONE)) return;
        if (isPrimeBig(n)) {
            mp.put(n, mp.getOrDefault(n, 0) + 1);
            return;
        }
        BigInteger d = rho(n, rnd);
        factor(d, mp, rnd);
        factor(n.divide(d), mp, rnd);
    }

    // 2x2 矩阵乘法（模 MOD）
    static long[][] mul(long[][] A, long[][] B) {
        long[][] C = new long[2][2];
        C[0][0] = ( (A[0][0]*B[0][0])%MOD + (A[0][1]*B[1][0])%MOD )%MOD;
        C[0][1] = ( (A[0][0]*B[0][1])%MOD + (A[0][1]*B[1][1])%MOD )%MOD;
        C[1][0] = ( (A[1][0]*B[0][0])%MOD + (A[1][1]*B[1][0])%MOD )%MOD;
        C[1][1] = ( (A[1][0]*B[0][1])%MOD + (A[1][1]*B[1][1])%MOD )%MOD;
        return C;
    }

    static long[][] mpow(long[][] A, long e) {
        long[][] R = new long[][]{{1,0},{0,1}};
        long[][] B = new long[][]{{A[0][0],A[0][1]},{A[1][0],A[1][1]}};
        while (e > 0) {
            if ((e & 1L) == 1L) R = mul(R, B);
            B = mul(B, B);
            e >>= 1;
        }
        return R;
    }

    // 计算固定指数 e 的长度 L 序列数 T_e(L)
    static long countForExp(long e, long L) {
        long eMod = e % MOD;
        if (L == 1) return (1 + eMod) % MOD;
        long[][] A = new long[][]{{1,1},{eMod,0}};
        long[][] P = mpow(A, L - 1);
        long dpE = ( (P[0][0]*1)%MOD + (P[0][1]*eMod)%MOD )%MOD;
        long dpL = ( (P[1][0]*1)%MOD + (P[1][1]*eMod)%MOD )%MOD;
        return (dpE + dpL) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();          // n ≤ 1e18
        sc.close();

        // 分解 n
        Map<BigInteger, Integer> mp = new HashMap<>();
        factor(BigInteger.valueOf(n), mp, new Random(123456));

        long ans = 1L;
        for (Map.Entry<BigInteger,Integer> e : mp.entrySet()) {
            long exp = e.getValue();
            ans = (ans * countForExp(exp, n)) % MOD;
        }
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using u128 = __uint128_t;
const long long MOD = 1'000'000'007LL;

// --- 快速乘幂（用于 Miller-Rabin） ---
u64 mul_mod(u64 a, u64 b, u64 mod){
    return (u128)a * b % mod;
}
u64 pow_mod(u64 a, u64 e, u64 mod){
    u64 r = 1;
    while(e){
        if(e & 1) r = mul_mod(r, a, mod);
        a = mul_mod(a, a, mod);
        e >>= 1;
    }
    return r;
}

// --- Miller-Rabin 判素（64 位确定性底集合） ---
bool is_prime_u64(u64 n){
    if(n < 2) return false;
    for(u64 p: {2ull,3ull,5ull,7ull,11ull,13ull,17ull,19ull,23ull,29ull,31ull,37ull}){
        if(n%p==0) return n==p;
    }
    u64 d = n-1, s = 0;
    while((d & 1)==0){ d >>= 1; ++s; }
    auto witness = [&](u64 a)->bool{
        u64 x = pow_mod(a, d, n);
        if(x==1 || x==n-1) return false;
        for(u64 i=1;i<s;i++){
            x = mul_mod(x, x, n);
            if(x==n-1) return false;
        }
        return true;
    };
    for(u64 a: {2ull,3ull,5ull,7ull,11ull,13ull,17ull,19ull,23ull,29ull,31ull,37ull}){
        if(a % n == 0) return true;
        if(witness(a)) return false;
    }
    return true;
}

// --- Pollard-Rho ---
u64 rng64(){
    static mt19937_64 rng(1234567);
    return rng();
}
u64 pollard(u64 n){
    if(n%2ull==0ull) return 2ull;
    while(true){
        u64 c = rng64()%(n-1)+1;
        u64 x = rng64()%n, y = x, d = 1;
        auto f = [&](u64 v){ return (mul_mod(v, v, n) + c) % n; };
        while(d==1){
            x = f(x);
            y = f(f(y));
            u64 diff = x>y ? x-y : y-x;
            d = std::gcd(diff, n);
        }
        if(d!=n) return d;
    }
}
void factor(u64 n, map<u64,int>& mp){
    if(n==1) return;
    if(is_prime_u64(n)){ mp[n]++; return; }
    u64 d = pollard(n);
    factor(d, mp);
    factor(n/d, mp);
}

// --- 2x2 矩阵（模 MOD） ---
struct Mat {
    long long a00,a01,a10,a11;
};
Mat mulM(const Mat& A, const Mat& B){
    Mat C;
    C.a00 = ( (A.a00*B.a00)%MOD + (A.a01*B.a10)%MOD )%MOD;
    C.a01 = ( (A.a00*B.a01)%MOD + (A.a01*B.a11)%MOD )%MOD;
    C.a10 = ( (A.a10*B.a00)%MOD + (A.a11*B.a10)%MOD )%MOD;
    C.a11 = ( (A.a10*B.a01)%MOD + (A.a11*B.a11)%MOD )%MOD;
    return C;
}
Mat powM(Mat A, unsigned long long e){
    Mat R{1,0,0,1};
    while(e){
        if(e&1) R = mulM(R, A);
        A = mulM(A, A);
        e >>= 1;
    }
    return R;
}

// 固定指数 e，长度 L 的计数 T_e(L)
long long countForExp(long long e, unsigned long long L){
    long long em = e % MOD;
    if(L==1ull) return (1 + em) % MOD;
    Mat A{1,1,em,0};
    Mat P = powM(A, L-1);
    // vL = P * [1, e]^T
    long long dpE = ( (P.a00*1)%MOD + (P.a01*em)%MOD )%MOD;
    long long dpL = ( (P.a10*1)%MOD + (P.a11*em)%MOD )%MOD;
    return (dpE + dpL) % MOD;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long n;
    if(!(cin >> n)) return 0;

    map<u64,int> mp;
    factor(n, mp);

    long long ans = 1;
    for(auto &kv : mp){
        long long e = kv.second;
        ans = (ans * countForExp(e, n)) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

题目内容

小美有一个正整数 $n$，小美想要构造一个长度为 $n$ 的正整数数组 $a$ ，满足 $\forall 1 ≦i<n,lcm(a_i,a_{i+1})= n$ ，也就是对于数组任意相邻两项的最小公倍数都等于 $n$ 。

但是小美觉得这个问题太简单了，所以希望你帮他求出一共有多少个数组 $a$ 满足这个条件。

由于答案可能很大，请将答案对 $10^9+7$ 取模后输出。

输入描述

输入一个正整数 $n (2 ≦ n ≦ 10^{18})$。

输出描述

输出一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例1

输入

114514

输出

159196343