LightOJ – 1282 求取数字前三位和后三位

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

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

Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

Output
For each case, print the case number and the three leading digits (most significant) and three trailing 
Read the rest

LightOJ – 1138 Trailing Zeroes (III)

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

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

Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.

Output
For each case, print the case number and N. If 
Read the rest

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 
Read the rest

线性同余方程组的合并

类似于

$$a_ix\equiv b_i\mod m_i$$

的方程组就是线性同余方程组
根据同余的可加性,可令

$$x\equiv B \mod lcm(m_i) $$

所以答案就转化为了求B和lcm

$$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

$$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)$$

把t带入

$$x=B_1+m_1*t $$

$$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); //无解
		
Read the rest

【容斥原理】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}, 
Read the rest

【矩阵快速幂】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
Read the rest

【离线并查集】问题集合

  • 有 N 个数,初始均为 0。有 Q 个操作,第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问,所有操作结束后,每个数的值

并查集维护每个点右边最近的未修改的点,把操作全部读入以后倒序处理,因为是倒着处理所以每个点只能被修改一次,直接用数组记录就可以了。初始f[i]=i;当l..r合并以后区间内每个f[i]=i+1;查询函数加上路径压缩,当遇见一个被改变过的点可以立刻跳过后面所有被改变了的点

#include<iostream>
#include<stdio.h>
using namespace std;
int f[1001]={0};
int qm[1001][3]={0};
int a[1001]={0};
int n=0,q=0;
int ff(int x)
{
	if(f[x]==x) return x;
	else return f[x]=ff(f[x]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n+2;i++) f[i]=i;
	for(int i=q;i>0;i--)
	{
		scanf("%d%d%d",&qm[i][1],&qm[i][2],&qm[i][0]);
	}
	for(int i=1;i<=q;i++)
	{
		int l=qm[i][1],r=qm[i][2],v=qm[i][0];
		while(l<=r)
		{			
			l=ff(l);
			if(l<=r)
			{
				a[l]=v;
				f[l]=l+1;
				l+=1;
			}
			else
			{
				break;
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
} 

 … Read the rest

【坑】高数满分—pow的问题

Description

众所周知,qm的高数总是满分。这一天数学白痴锦鱼拿着一道数学题来问qm,qm不屑做这种简单的题,于是把这道题丢给你来完成。题目是这样的:给定a、b、c三个整数,求最大的整数x,满足xa+b*x<=c,其中xa表示x的a次方,b*x表示b乘以x。

Input

第一行输入三个整数a(1<=a<=10),b(0<=b<=1018),c(0<=c<=1018),分别对应题目中a、b、c三个整数。

Output

输出一个整数,表示所求的最大的x。

Sample Input

2 3 4

Sample Output

1
这题虽然是一道二分,但由于x^a可能过于大,所以x每次要去pow(c,1.0/a)避免爆炸。
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;
	
Read the rest

【数学-贪心-末状态已知】问题集合

  • 蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”:因为非齐次方程组的系数行列式为0,所以方程的解不唯一,所以最后一个方程没有贡献。

末态相同的题目,可以往方程组方向去想。最后可以往坐标的距离方面去靠。

  • 蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明:

设开始每个墓碑相差A,移动后每个墓碑相差M,M可以不相同,因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

$$A-X_1+X_2=M =>X_2=X_1-(A-M)$$

$$A-X_2+X_3=M =>X_3=X_1-2(A-M)$$

$$…$$

$$A-X_n+X_1=M =>X_n=X_1-n(A-M)$$

 

同样可以变成X1到各个数字的距离最小的问题,即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案,因为M仅仅是假设存在一个M使其满足末态,由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest