挑战程序竞赛系列（41）：4.1中国剩余定理

POJ 1006: Biorhythms

x≡1mod5x≡2mod6x≡3mod7

x \equiv 1 \mod 5 \\ x \equiv 2 \mod 6 \\ x \equiv 3 \mod 7 \\

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201708/P1006.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

void solve() {
int t = 0;
while (true){
int p = ni();
int e = ni();
int i = ni();
int d = ni();
if (p == -1 && e == -1 && i == -1 && d == -1) break;
int[] a = new int[3];
int[] m = new int[3];
a[0] = p;
a[1] = e;
a[2] = i;
m[0] = 23;
m[1] = 28;
m[2] = 33;
int ans = CRT(a, m, 3);
if (ans <= d){
ans += 21252;
}
out.println("Case " + (++t) + ": the next triple peak occurs in " + (ans - d) + " days.");
}
}

class Pair{
int d;
int x;
int y;
public Pair(int d, int x, int y){
this.d = d;
this.x = x;
this.y = y;
}
}

public Pair extgcd(int a, int b){
if (b == 0){
return new Pair(a, 1, 0);
}
else{
Pair p = extgcd(b, a % b);
Pair ans = new Pair(0, 0, 0);
ans.d = p.d;
ans.x = p.y;
ans.y = p.x - (a / b) * p.y;
return ans;
}
}

public int mod_inverse(int a, int m){
Pair p = extgcd(a, m);
if (p.d != 1) return -1;
return (p.x % m + m) % m;
}

public int CRT(int[] a, int[] m, int n){
int M = 1;
int ans = 0;
for (int i = 0; i < n; ++i){
M *= m[i];
}
for (int i = 0; i < n; ++i){
int inv = mod_inverse(M / m[i], m[i]);
ans += a[i] * M / m[i] * inv;
ans %= M;
}
return ans;
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}

POJ 2891: Strange Way to Express Integers

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201708/P2891.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

void solve() {
while (more()){
int n = ni();
long[] a = new long[n];
long[] m = new long[n];
for (int i = 0; i < n; ++i){
m[i] = ni();
a[i] = ni();
}
out.println(CRT(a, m, n));
}
}

class GCD{
long d;
long x;
long y;

public GCD(long d, long x, long y){
this.d = d;
this.x = x;
this.y = y;
}
}

public long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}

public GCD extgcd(long a, long b){
if (b == 0) return new GCD(a, 1, 0);
else{
GCD g   = extgcd(b, a % b);
GCD ans = new GCD(0, 0, 0);
ans.d = g.d;
ans.x = g.y;
ans.y = g.x - (a / b) * g.y;
return ans;
}
}

public long mod_inverse(long a, long m){
GCD g = extgcd(a, m);
if (g.d != 1) return -1;
return (g.x % m + m) % m;
}

class LL{
long val;

public LL(){}

public LL(long val){
this.val = val;
}

@Override
public String toString() {
return val + "";
}
}

public boolean merge(long a1, long m1, long a2, long m2, LL a3, LL m3){
GCD g = extgcd(m1, m2);
long c = a2 - a1;
long d = g.d;
if (c % d != 0) return false;
m1 /= d;
m2 /= d;
c  /= d;
long inv = mod_inverse(m1, m2);
c *= inv;
c %=  m2;
c *= m1 * d;
c += a1;
m3.val = m1 * m2 * d;
a3.val = c;
return true;
}

public long CRT(long[] a, long[] m, int n){
long a1 = a[0];
long m1 = m[0];
for (int i = 1; i < n; ++i){
long a2 = a[i];
long m2 = m[i];

LL a3 = new LL();
LL m3 = new LL();
if (!merge(a1, m1, a2, m2, a3, m3)) return -1;

a1 = a3.val;
m1 = m3.val;
}
return (a1 % m1 + m1) % m1;
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}

POJ 3708: Recurrent Function

f(d×n+j)=d×f(n)+bj

f (d \times n + j) = d \times f(n) + b_j 你能想到什么？它实际上是一种m转d进制，这是思维上的突破，想到这点后续都简单了。

f(m)=ap1⋅dn−1+∑i=2n(bpi⋅dn−i),ap1ϵ[1，d）,(bpiϵ[0,d),iϵ[2,n)]

f(m) = a_{p_1} \cdot d ^{n - 1} + \sum_{i=2}^n( {b_{p_i}}\cdot d ^{n - i}) , a_{p_1}\epsilon[1，d）, (b_{p_i}\epsilon[0, d),i\epsilon[2, n)]

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201708/P3708.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

int[] A;
int[] B;

void solve() {
while (true){
int N = ni();

if (N == -1) break;

A = new int[N];
B = new int[N];

for (int i = 1; i < N; ++i){
A[i] = ni();
}

for (int i = 0; i < N; ++i){
B[i] = ni();
}
String m = ns();
String k = ns();

int[] nm = new int[m.length() + 16];
for (int i = m.length() - 1; i >= 0; --i) nm[i] = m.charAt(i) - '0';
int[] nk = new int[k.length() + 16];
for (int i = k.length() - 1; i >= 0; --i) nk[i] = k.charAt(i) - '0';

LEN_M = tran(nm, m.length(), M, N);
LEN_K = tran(nk, k.length(), K, N);

if (LEN_M != LEN_K) out.println("NO");
else{
getRC(LEN_M);
boolean valid = true;
for (int i = 0; i < LEN_M; ++i){
if (C[i] == -1){
valid = false;
break;
}
}
if (!valid) out.println("NO");
else{
long ans = CRT(C, R, LEN_M);
if (ans == -1) out.println("NO");
else{
out.println(ans);
}
}
}
}
}

/********************欧几里德两两合并***************************/
class GCD{
long d;
long x;
long y;

public GCD(long d, long x, long y){
this.d = d;
this.x = x;
this.y = y;
}
}

public long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}

public GCD extgcd(long a, long b){
if (b == 0) return new GCD(a, 1, 0);
else{
GCD g   = extgcd(b, a % b);
GCD ans = new GCD(0, 0, 0);
ans.d = g.d;
ans.x = g.y;
ans.y = g.x - (a / b) * g.y;
return ans;
}
}

public long mod_inverse(long a, long m){
GCD g = extgcd(a, m);
if (g.d != 1) return -1;
return (g.x % m + m) % m;
}

class LL{
long val;

public LL(){}

public LL(long val){
this.val = val;
}

@Override
public String toString() {
return val + "";
}
}

public boolean merge(long a1, long m1, long a2, long m2, LL a3, LL m3){
GCD g = extgcd(m1, m2);
long c = a2 - a1;
long d = g.d;
if (c % d != 0) return false;
m1 /= d;
m2 /= d;
c  /= d;
long inv = mod_inverse(m1, m2);
c *= inv;
c %=  m2;
c *= m1 * d;
c += a1;
m3.val = m1 * m2 * d;
a3.val = c;
return true;
}

public long CRT(int[] a, int[] m, int n){
long a1 = a[0];
long m1 = m[0];
for (int i = 1; i < n; ++i){
long a2 = a[i];
long m2 = m[i];

LL a3 = new LL();
LL m3 = new LL();
if (!merge(a1, m1, a2, m2, a3, m3)) return -1;

a1 = a3.val;
m1 = m3.val;
}
return (a1 % m1 + m1) % m1;
}

/****************大数进制转换****************/
int MAX_D = 500 + 16;
int[] M = new int[MAX_D];
int[] K = new int[MAX_D];
int LEN_M;
int LEN_K;

public int tran(int ten[], int len, int ans[], int d){
int cnt = 0;
int tcnt = 0;
while(tcnt < len){

for(int i = tcnt; i < len; ++i){
ten[i + 1] += (ten[i] % d) * 10;
ten[i] /= d;
}/**模拟除法,余数 * 10存在ten[len]中*/

ans[cnt++] = ten[len] / 10;
ten[len] = 0;
while(ten[tcnt] == 0 && tcnt < len) ++tcnt;
}
return cnt;
}

/***************************计算每一位的模数****************************/
int[] R = new int[MAX_D];
int[] C = new int[MAX_D];

// 获得模数
public void getRC(int len){
Arrays.fill(C, -1);
int id = len - 1;
R[id] = 1;
int cnt = 0;
if (M[id] == K[id]) C[id] = 0;
for (int i = A[M[id]]; i != M[id]; i = A[i]){
++R[id];
++cnt;
if (i == K[id]) C[id] = cnt;
}

for (int i = 0; i < id; ++i){
if (K[i] == M[i]) C[i] = 0;
R[i] = 1;
cnt  = 0;
for (int j = B[M[i]]; j != M[i]; j = B[j]){
++R[i];
++cnt;
if (K[i] == j) C[i] = cnt;
}
}
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}

0 条评论

• LeetCode Weekly Contest 29解题思路

代码很简单，简单说明下思路就出来了。按照题意，不管怎么二分，整个数组都会被划分成两部分和，这两部分和必然一大一小。如nums = [1,4,3,2]，划分如下[...

• 挑战程序竞赛系列（74）：4.3强连通分量分解（1）

挑战程序竞赛系列（74）：4.3强连通分量分解（1） 传送门：POJ 2186: Popular Cows 题意： 每头牛都想成为牛群中的红人。给定N头牛的牛...

• 挑战程序竞赛系列（70）：4.7后缀数组（2）

挑战程序竞赛系列（70）：4.7后缀数组（2） 传送门：POJ 1509: Glass Beads 题意： The description of the ne...

• 10个常见的 Java 错误及避免方法之第二集（后续持续发布）

当程序缺少关闭大括号（“}”）时，Java代码中就会发生此错误消息。 有时我们可以通过在代码的末尾放置大括号来快速修复错误。

• LeetCode Weekly Contest 29解题思路

代码很简单，简单说明下思路就出来了。按照题意，不管怎么二分，整个数组都会被划分成两部分和，这两部分和必然一大一小。如nums = [1,4,3,2]，划分如下[...

• LeetCode 441. 排列硬币（数学解方程）

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

• Java能写外挂吗？那就写个跳一跳辅助程序吧

##起初是想使用按键精灵脚本程序控制，但还是选择熟悉的java。我这里使用了工具，造成延迟问题。也求教：java控制安卓的正确姿势，

• 挑战程序竞赛系列（94）：3.6凸包（5）

挑战程序竞赛系列（94）：3.6凸包（5） 传送门：POJ 2079: Triangle 题意： 求三个点构成的最大三角形面积。 思路： 可以证明，三点构...

• 挑战程序竞赛系列（91）：3.6凸包（2）

挑战程序竞赛系列（91）：3.6凸包（2） 传送门：POJ 1113: Wall 题意参考hankcs： http://www.hankcs.com/pro...

• 挑战程序竞赛系列（90）：3.6凸包（1）

挑战程序竞赛系列（90）：3.6凸包（1） 传送门：POJ 2187: Beauty Contest 题意： 平面上有N个牧场。i号牧场的位置在格点(xi,y...