【gdgzezoi】Problem B:毎日走るのが好き

Description
Cさんはランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.「毎日走るのが好き」は育成ゲームで、プレイヤーが毎日時間通りにオンラインになり、カードを打つ任務を完成する必要がある.
このゲームの地図は,n個のノードとn−1個のエッジを含む木と見なすことができ,各エッジが2個のノードを接続し,任意の2つのノードが1つの経路で互いに達することができる.ツリー上のノード番号は、1からnまでの連続正の整数です.
現在mプレイヤーがおり,i番目のプレイヤーの起点はSi,終点はTiである.毎日カードを打つ任務が始まる時、すべてのプレーヤーは0秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、間断なく最短の経路に沿って自分の終点に向かって走って、終点に着いた後にそのプレーヤーはカードを打つ任務を完成しました.(地図は木なので、一人一人の経路は唯一です)
Cちゃんはゲームの活躍度が知りたくて、ノードごとにオブザーバーが置かれていました.ノードjのオブザーバーは、Wj秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーがWj秒目にちょうどノードjに到着したときにのみ観察することができる.
しかし、Cさんはゲーム作りに夢中になっていたため、国家合宿チームの一員であることや、156の宿題問題などを完全に忘れてしまった.あと1日で宿題が終わるが,彼はまだ1題もやっていない.そこで彼は急いで最も簡単に見える問題を選んだ.
「整数Nを指定すると、1からKの間の整数の文字列がどれだけあるかを求めてください.これにより、その文字列は長さNの文字列から循環シフトして得ることができます.循環シフトとは、文字列のある接頭辞(空でもよい)を文字列の末尾に移動することです.例えば、「1221」の循環シフトでは「1221」、「2211」、「2112」、「1122」が得られます4つの文字列.結果は109+7で型を取ります.」
Cさんの合宿チームの資格がCCFに取り消されないように、この問題を完成させてください.
Input
第1行は2つの整数N,Kを含む.
Output
条件を満たす文字列数対109+7の型取りの結果を出力します.Sample Input
Sample Input 1
4 2
Sample Input 2
1 10
Sample Input 3
6 3
Sample Input 4
1000000000 1000000000 Sample Output
Sample Output 1
6
Sample Output 2
10
Sample Output 3
75
Sample Output 4
875699961
HINT
最初の例では、「1111」、「1122」、「1221」、「2211」、「2112」、「2222」の6文字列が条件を満たしている.
データ範囲:1≦N,K≦109
10分のサブタスクが存在し、1≦N、K≦10を満たす.20分のサブタスク(前のサブタスクとは独立)が存在し、1≦N,K≦2000を満たす.
構想
まず、回転の制限がなければ明らかに(n/2)mであり、回転すると理論的にはnに乗るが、明らかに重い
計算が重いのは、いくつかの回文列がテーマの中の方法で互いに到着できるからです.では、私たちは各回文列から次の回文列までのステップを計算するだけでいいです.
ステップ数はこの文字列のループ・セクションに関係していることが容易にわかります.1つの文字列の長さが偶数であれば、ステップ数は長さ/2であり、そうでなければループ・セクションの長さです.
ここで我々の問題は,各長さのループ節に対応する文字列がどれだけあるかを求め,このループ節がすべての文字列に対応する最小ループ節であるようにf[x]が最小ループ節をxとする文字列を表すスキーム数を設定すると,f[x]=((x+1)/2)m然後にループ節をさらに小さく減算する
コード#コード#

#include
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int N=2e5+20;
vector<ll> v;
ll n,k,f[2500];
ll power(ll x,ll n)
{
    ll s=1;
    while(n)
    {
        if(n&1) s=(s*x)%mod;
        n>>=1;
        x=(x*x)%mod;
    }
    return s;
}
void init()
{
    v.clear();
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            v.push_back(i);
            if(i*i!=n) v.push_back(n/i);
        }
    }
    sort(v.begin(),v.end());
}
int main()
{
    scanf("%d%d",&n,&k);
    init();
    ll ans=0;
    for(int x=0;x<v.size();x++)
    {
        f[x]=power(k,(v[x]+1)/2);
        for(int y=0;y<x;y++)
        {
            if(v[x]%v[y]==0) f[x]=(f[x]-f[y]+mod)%mod;  
        }   
        if(v[x]%2) ans=(ans+(f[x]*v[x])%mod)%mod;
        else ans=(ans+(f[x]*v[x]/2)%mod)%mod;
    }
    printf("%lld",ans);
}