## LightOJ – 1045 K进制的位数

Factorial of an integer is defined by the following function

f(0) = 1

f(n) = f(n - 1) * n, if(n > 0)

So, factorial of 5 is 120. But in different bases, the factorial may be different. For example, factorial of 5 in base 8 is 170.

In this problem, you have to find the number of digit(s) of the factorial of an integer in a certain base.

Input
Input starts with an integer T (≤ 50000), denoting the 

## 线性同余方程组的合并



a_ix\equiv b_i\mod m_i

x\equiv B \mod lcm(m_i)

a_1x \equiv b_1 \mod m1

x\equiv (b_1/\gcd(a_1,m_1))*(a_1^{-1}/gcd(a_1,m_1)) \mod (m_1/gcd(a_1,m_1))

x \equiv B_1 \mod m1

x=B_1+m_1*t 此时的m1*t是未知的

a(B_1+m_1t) \equiv b_2 \mod m_2

am_1t \equiv b_2-aB_1 \mod m_2

t \equiv (b_2-aB_1)/gcd(am_1,m_2) * (am_1)^{-1}/gcd(am_1,m_2) \mod (m_2)/gcd(am_1,m_2)

x=B_1+m_1*t

$此时的x在\mod m1和\mod m2的意义下都是成立的。B1_+m_1*t变成了新的B_2$

x\equiv B_2 \mod lcm(m_1,m_2)

x=B_2+lcm*t

//返回一个b，m对
pair<int, int> inner_congruence(const vector<int> &A,const vector<int> &B,const vector<int> &M)
{
int x=0,m=1;
for(int i-9;i<A.size();i++)
{
int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(a,M[i]);
if(b%d!=0) return make_pair(0,-1); 

## 【容斥原理】Arrange the Numbers LightOJ – 1095

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

For Example, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, 

## 【矩阵快速幂】nth Term LightOJ – 1096

You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

= 0, if(n ≤ 2)

Input
Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input


## Sample Input

2 3 4

## Sample Output

1


xyjj说pow在计算longlong的时候会出现各种奇怪的问题（导致我WA了无数次），后来网上查了一下说是因为pow是计算的double所以会有精度丢失的问题，所以二分里面的pow要自己写……………….
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a,b,c;
ll qkpow(ll x,int p)
{
if(p==0) return 1;
if(p==1) return x;

ll y=qkpow(x,p>>1);

y=y*y;

if(p&1)
y=y*x;

return y;
}
int main()
{
cin>>a>>b>>c;
ll l=0,r=(ll)pow((double)c,1.0/a);
//if(b!=0) r=c/b;
//r=min(r,(ll)pow(c,1.0/a));
while(r-l>1)
{
ll mid=(r+l)>>1;
if(qkpow(mid,a)+b*mid<=c)
{
l=mid;
}
else
{
r=mid;
}
}
if(qkpow(r,a)+r*b<=c) cout<<r;