Ryan_<

关于Educational Codeforces Round ：

1、定位于新人学习和训练= =

2. 题目不仅有比赛的problems，还可能会有训练的exercises

3. 题目的考察点可能会被反复使用

4. 不参与计算rating（至少目前是）

5. 比赛的编码阶段和hack阶段分开，编码结束之后的结果是暂时的

6. 编码阶段结束之后，开放24小时的hack，hack的数据可能会被添加到最终的测试数据中去

7. 最终测试数据确定之后的测试结果作为比赛结果

A.Johny Likes Numbers

求大于n的最小的K的倍数。（1<=n,k<=10^9)

O（1）公式题

ans=(n/K+1)*K. 注意K与n大小关系不确定.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,K;
int main()
{
	scanf("%lld%lld",&n,&K);
	printf("%lld",(n/K+1)*K);
	return 0;
}

B. The Same Calendar

求给出年份y之后第一个与y的日期(星期几)完全相同的年份。注意闰年。(1000<=y<=1000,000)

我赛后被hack了!【数据待补充】

要求的年份与y相差天数%7==0,且平/闰年一致。

bool check(int p)
{
    if(p%400==0)return 1;
    if(p%4==0&&p%100!=0)return 1;
    return 0;
}

【待改正】

C. Joty and Chocolate

1~n的序列，编号为a倍数的元素可获得p块巧克力，编号为b倍数的元素可获得q块巧克力，满足的条件不可累加，求最多获得的巧克力数。(1 ≤ n, a, b, p, q ≤ 10^9)

将编号为lcm(a,b)的元素分给获得巧克力数多的那个，整体计算。

LL gcd(LL x,LL y)
{
	if(!y) return x;
	return gcd(y,x%y);
}
LL lcm(LL x,LL y)
{
	return x*y/gcd(x,y);
}

D. Iterated Linear Function

定义函数f(x)=A*x+B,

g(0)(x)=x;

g(n)(x)=f(g(n-1)(x)),(n>0)

给定A,B,n,x求g(n)(x)%(10^9+7)

1 ≤ A, B, x ≤ 10^9, 1 ≤ n ≤ 10^18

非常经典的题目了吧！O(logN)的做法有两种：

1、矩阵乘法：初始矩阵S=[x,1]，转移矩阵T=[[A,0],[B,1]]，S*T^n%MOD

2、等比数列求和推通项公式，结合快速幂，费马小定理求逆元。

注意要特判A==1的情况！

#include<bits/stdc++.h>
#define F(i,s,t) for(int i=(s);i<=(t);i++)
#define mec(a,x) memset(a,x,sizeof(a)) 
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL A,B,x,n;
struct matrix{
	LL c[3][3];//大一点木事 
	void init(){mec(c,0);}
	friend matrix operator *(const matrix &S,const matrix &T){
		matrix res;
		F(i,1,2) F(j,1,2){
			res.c[i][j]=0;
			F(k,1,2) res.c[i][j]=(res.c[i][j]+S.c[i][k]*T.c[k][j])%MOD;
		}
		return res;
	}
}t,ans;
void matrix_pow()
{
	ans.c[1][1]=x;ans.c[1][2]=1;
	while(n){
		if(n&1) ans=ans*t;
		t=t*t;
		n>>=1;
	}
}
int main()
{
	scanf("%lld%lld%lld%lld",&A,&B,&n,&x);
	t.init();ans.init();
	t.c[1][1]=A;t.c[2][1]=B;
	t.c[1][2]=0;t.c[2][2]=1;
	matrix_pow();
	printf("%lld\n",ans.c[1][1]);
	return 0;
}