Solved:2
rank:293
J. Sequense
不知道自己写的什么东西 以后整数分块直接用 n / (n / i)表示一个块内相同n / i的最大i
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + ;
ll A, B, C, D, P, n;struct martix
{
ll c[][];
};martix mul(martix A, martix B)
{
martix res;
memset(res.c, , sizeof(res.c));
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
for(int k = ; k < ; k++)
res.c[i][j] = (res.c[i][j] + A.c[i][k] * B.c[k][j] % mod) % mod, (res.c[i][j] += mod) %= mod;
return res;
}martix pow_mod(martix x, ll y)
{
martix res;
memset(res.c, , sizeof(res.c));
res.c[][] = res.c[][] = res.c[][] = 1LL;
while(y)
{
if(y & ) res = mul(res, x);
x = mul(x, x);
y >>= ;
}
return res;
}int main()
{
martix og; int T;
scanf("%d", &T);
while(T--)
{
scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
memset(og.c, , sizeof(og.c));
og.c[][] = D + ;
og.c[][] = C - D;
og.c[][] = -C;
og.c[][] = og.c[][] = ; ll f1 = A;
ll f2 = B;
if(n == )
{
printf("%lld\n", A);
continue;
}
if(n == )
{
printf("%lld\n", B);
continue;
} if(n <= )
{
for(int i = ; i <= n; i++)
{
ll tmp = f1 * C % mod + D * f2 % mod + P / i;
tmp %= mod;
f1 = f2;
f2 = tmp;
}
printf("%lld\n", f2);
continue;
} for(int i = ; i <= ; i++)
{
ll tmp = f1 * C % mod + D * f2 % mod + P / i;
tmp %= mod;
f1 = f2;
f2 = tmp;
} ll now = ;
ll f3 = C * f1 % mod + D * f2 % mod + P / now; f3 %= mod;
//cout<<f3<<endl;
ll ans = f3;
while(now < n)
{
if(P / now == P / n)
{
ans = ;
martix tmp1 = pow_mod(og, n - now);
ans = tmp1.c[][] * f3 % mod + tmp1.c[][] * f2 % mod; ans %= mod;
ans += tmp1.c[][] * f1 % mod; ans %= mod;
ans += mod; ans %= mod;
break;
} if(now + >= n)
{
for(int i = now + ; i <= n; i++)
{
ll ttmp = f2 * C % mod + D * f3 % mod + P / i;
ttmp %= mod;
f1 = f2;
f2 = f3;
f3 = ttmp;
}
ans = f3;
break;
} if(P / (now + ) != P / now)
{
for(int i = now + ; i <= now + ; i++)
{
ll tymp = f2 * C % mod + D * f3 % mod + P / i;
tymp %= mod;
f1 = f2;
f2 = f3;
f3 = tymp;
}
now += ;
continue;
} ll l = now, r = n;
ll mid = l + r >> ;
while(l + < r)
{
mid = l + r >> ;
if(P / mid == P / now) l = mid;
else r = mid;
} ll opp;
if(P / r == P / now) opp = r;
else opp = l; if(opp - now >= )
{
martix tmp2 = pow_mod(og, opp - now - );
ll tt = ;
tt = tmp2.c[][] * f3 % mod + tmp2.c[][] * f2 % mod; tt %= mod;
tt += tmp2.c[][] * f1 % mod; tt %= mod;
tt += mod; tt %= mod; tmp2 = mul(tmp2, og);
ll ttt = ;
ttt = tmp2.c[][] * f3 % mod + tmp2.c[][] * f2 % mod; ttt %= mod;
ttt += tmp2.c[][] * f1 % mod; ttt %= mod;
ttt += mod; ttt %= mod; f1 = tt;
f2 = ttt;
f3 = C * f1 % mod + D * f2 % mod + P / opp;
f3 %= mod;
now = opp;
}
else
{
for(int i = now + ; i <= opp; i++)
{
ll tmpp = C * f2 % mod + D * f3 % mod + P / i;
tmpp %= mod;
f1 = f2;
f2 = f3;
f3 = tmpp;
}
now = opp;
}
}
printf("%lld\n", ans);
}
return ;
}