P1226 【模板】快速幂
题目描述
给你三个整数 𝑎,𝑏,𝑝a,b,p，求 𝑎𝑏 mod 𝑝abmodp。
输入格式
输入只有一行三个整数，分别代表 𝑎,𝑏,𝑝a,b,p。
输出格式
输出一行一个字符串
a^b mod p=s，其中 𝑎,𝑏,𝑝a,b,p 分别为题目给定的值， 𝑠s 为运算结果。输入输出样例
输入 #1复制
2 10 9输出 #1复制
2^10 mod 9=7说明/提示
样例解释
210=1024210=1024，1024 mod 9=71024mod9=7。
数据规模与约定
对于 100%100% 的数据，保证 0≤𝑎,𝑏<2310≤a,b<231，𝑎+𝑏>0a+b>0，2≤𝑝<2312≤p<231。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
static long nextLong() throws IOException{
st.nextToken();
return (long)st.nval;
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
long a=nextLong();
long b=nextLong();
long q=nextLong();
long a1=a,b1=b;
long ans=1;
while(b>0) {
if(b%2==1)
ans=(ans*a)%q;
a=(a*a)%q;
b=b>>1;
}
System.out.println(a1 + "^" + b1 + " mod " + q + "=" + ans);
}
}P1010 [NOIP1998 普及组] 幂次方
题目描述
任何一个正整数都可以用 22 的幂次方表示。例如 137=27+23+20137=27+23+20。
同时约定次方用括号来表示，即 𝑎𝑏ab 可表示为 𝑎(𝑏)a(b)。
由此可知，137137 可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步：
7=22+2+207=22+2+20 ( 2121 用 22 表示)，并且 3=2+203=2+20。
所以最后 137137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)。
又如 1315=210+28+25+2+11315=210+28+25+2+1
所以 13151315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。
输入格式
一行一个正整数 𝑛n。
输出格式
符合约定的 𝑛n 的 0,20,2 表示（在表示中不能有空格）。
输入输出样例
输入 #1复制
1315输出 #1复制
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)说明/提示
【数据范围】
对于 100%100% 的数据，1≤𝑛≤2×1041≤n≤2×104。
NOIP1998 普及组 第三题
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(f.readLine());
calc(n);
}
static void calc(int n) {
if(n == 0)
return;
int exp=0;
while(n>=(1<<exp)){
exp++;
}
exp--;
n-=(1<<exp);
if(exp==0||exp==2){
System.out.print("2"+"("+exp+")");
}if(exp==1){
System.out.print("2");
}if(exp>2){
System.out.print("2"+"(");
calc(exp);
System.out.print(")");
}
if(n>0){
System.out.print("+");
calc(n);
}
}
} P1429 平面最近点对（加强版）
题目背景
P7883 平面最近点对（加强加强版）
题目描述
给定平面上 𝑛n 个点，找出其中的一对点的距离，使得在这 𝑛n 个点的所有点对中，该距离为所有点对中最小的
输入格式
第一行：𝑛n ，保证 2≤𝑛≤2000002≤n≤200000 。
接下来 𝑛n 行：每行两个实数：𝑥 𝑦x y ，表示一个点的行坐标和列坐标，中间用一个空格隔开。
输出格式
仅一行，一个实数，表示最短距离，精确到小数点后面 44 位。
输入输出样例
输入 #1复制
3 1 1 1 2 2 2输出 #1复制
1.0000说明/提示
数据保证 0≤𝑥,𝑦≤1090≤x,y≤109
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1000001;
const int INF = 2 << 20;
int n, temp[maxn];
struct Point
{
double x, y;
} S[maxn];
bool cmp(const Point &a, const Point &b)
{
if(a.x == b.x) return a.y < b.y;
else return a.x < b.x;
}
bool cmps(const int &a, const int &b) { return S[a].y < S[b].y; }
double min(double a, double b) { return a < b ? a : b; }
double dist(int i, int j)
{
double x = (S[i].x - S[j].x) * (S[i].x - S[j].x);
double y = (S[i].y - S[j].y) * (S[i].y - S[j].y);
return sqrt(x + y);
}
double merge(int left, int right)
{
double d = INF;
if(left == right) return d;
if(left + 1 == right) return dist(left, right);
int mid = left + right >> 1;
double d1 = merge(left, mid);
double d2 = merge(mid + 1, right);
d = min(d1, d2);
int i, j, k = 0;
for(i = left; i <= right; i++)
if(fabs(S[mid].x - S[i].x) < d) // 这里不太一样
temp[k++] = i;
sort(temp, temp + k, cmps);
for(i = 0; i < k; i++)
for(j = i + 1; j < k && S[temp[j]].y - S[temp[i]].y < d; j++)
{
double d3 = dist(temp[i], temp[j]);
if(d > d3) d = d3;
}
return d;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lf%lf", &S[i].x, &S[i].y);
sort(S, S + n, cmp);
return !printf("%.4lf\n", merge(0, n - 1));
}