LightOj-1370Bi-shoe and Phi-shoe
题目描述：
给出一些数字，对于每个数字找到一个欧拉函数值大于等于这个数的数，求找到的所有数的最小和。
求解：
(1)从题面来看没什么复杂的 ，考虑线性筛求欧拉函数 ， 直接对欧拉函数表查询
代码：
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
const int N = 1e6 + 10;
int phi[N];
bool isPrime[N];
int a[N];
void Eular(){
for(int i = 1;i <= N;i++) phi[i] = i;
memset(isPrime,true,sizeof isPrime);
isPrime[0] = isPrime[1] = false;
phi[1] = 0;
for(int i = 2;i <= N;i ++){
if(isPrime[i]){
for(int j = i;j <= N;j += i){
isPrime[j] = false;
phi[j] -= phi[j] / i;
}
}
}
}
int main(){
int T , n;
Eular();
cin >> T;
int cas = 0;
while(T--){
memset(a , 0 , sizeof a);
cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
ll sum = 0;
sort(a,a + n);
int pos = 1;
for(int i = 0;i < n;i++){
for(int j = pos;j < N;j++){
if(phi[j] >= a[i]){
sum += j;
pos = j;
break;
}
}
}
printf("Case %d: %lld Xukha\n",cas++,sum);
}
return 0;
}
LightOj-1341Aladdin and the Flying Carpet
题目描述：
给一对数字 a，b 。其中，a表示一个矩形的面积，想知道有多少种整数的边的组合可以组成面积为a的矩形，而且要求矩形的最短的边不得小于b给一对数字 a，b 。其中，a表示一个矩形的面积，想知道有多少种整数的边的组合可以组成面积为a的矩形，而且要求矩形的最短的边不得小于b
求解：
（1）给定矩形面积和最小边 ，都是正整数 ，所以可以转化为求区间[b , a] 之间 a的约数的个数
（2）复习下求约数个数
如果 N = p1^c1 * p2^c2 * ... *pk^ckc++
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
（3）至此题目转化为求正因子个数num，求出来之后/2，然后在枚举1-b 中属于a正因子的数， 用num减去就是我们要的答案。
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
const int N = 1e6 + 10;
int prime[N];
bool st[N];
int cnt;
typedef long long LL;
void init(){
cnt = 0;
st[1] = true;
for(int i = 2;i < N;i ++){
if(!st[i]){
prime[cnt ++] = i;
for(int j = i + i ;j < N;j += i) st[j] = true;
}
}
}
LL solve(LL n){
LL ans = 1;
for(int i = 0;i < tot && n;i++){
LL num = 0;
if(prime[i] > n) break;
while(n % prime[i] == 0){
n /= prime[i];
num ++;
}
ans *= (1 + num);
}
if(n > 1) ans *= 2; // 别忘了n > 1 时还剩个数
return ans;
}
int main(){
init();
LL s,q;
int T;
cin >> T;
int cas = 1;
while(T--){
scanf("%lld%lld",&s,&q);
if(q * q >= s){
printf("Case %d: 0\n",cas++);
continue;
}
LL res = solve(s);
num /= 2;
for(LL i = 1;i < q;i++)
if(s % i == 0) res--;
printf("Case %d: %lld\n" , cas++ , res);
}
return 0;
}
LightOj-1356Prime Independence
题目描述：
给出n个数，找出一个最大素数独立子集，如果a=b*一个素数，那么认为a是b的一个素数乘级，如果一个集合不存在一个数是另一个数的素数乘级，那么这就是素数独立子集。求这样的最大的子集大小。
求解：
（1）题面来看肯定与划分集合有关系 ，我们知道 P = a1^p1 *a2^p2 * a3^p3 * .......
如果P = p1*prime(k)的话：则p1如果含有偶数个素数因子，则P一定含有奇数个素数因子。
所以同为奇数偶数因子的两元素一定无关 ，他们俩可以划在一个集合 。
（2）（需要二分图匹配算法和HK优化来划分集合。。。。先鸽着）咕咕咕
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 40000+10
#define MAXM 1000000+10
#define INF 0x3f3f3f3f
#define debug printf("1\n");
using namespace std;
struct Edge{
int to, next;
};
Edge edge[MAXM];
int head[MAXN], edgenum;
int P[500010], num[500010];//记录每个数是否是质数 记录每个数里面质因子的个数
int a[MAXN];
int id[MAXN];
int oddnum, evennum;
void getP()
{
memset(P, 0, sizeof(P));
for(int i = 2; i <= 500000; i++)
{
if(P[i]) continue;
for(int j = 2*i; j <= 500000; j+=i)
P[j] = 1;
}
P[1] = 1;
}
//vector<int> p[500000+10];
void getPsum()
{
for(int j = 1; j <= 500000; j++)
{
int cnt = 0;
int n = j;
for(int i = 2; i * i <= n; i++)
{
if(n % i == 0)
{
while(n % i == 0)
{
cnt++;
n /= i;
}
}
}
if(n > 1)
cnt++;
num[j] = cnt;
}
}
void init(){
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v)
{
Edge E1 = {v, head[u]};
edge[edgenum] = E1;
head[u] = edgenum++;
}
int n;
int vis[500010];
int p[30], top;
void getprime(int n)
{
top = 0;
for(int i = 2; i * i <= n; i++)
{
if(n % i == 0)
{
p[top++] = i;
while(n % i == 0)
n /= i;
}
}
if(n > 1)
p[top++] = n;
}
void getMap()
{
scanf("%d", &n);
oddnum = evennum = 0;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
vis[a[i]] = i;//标记该元素 已经出现过
if(num[a[i]] & 1)
id[i] = ++oddnum;
else
id[i] = ++evennum;
}
init();
for(int i = 1; i <= n; i++)
{
getprime(a[i]);//处理质因子
for(int j = 0; j < top; j++)
{
int goal = a[i] / p[j];
int index = vis[goal];
if(index)//存在
{
if(num[a[i]] & 1 && num[a[index]] % 2 == 0)
addEdge(id[i], id[index]);
else if(num[a[i]] % 2 == 0 && num[a[index]] & 1)
addEdge(id[index], id[i]);
}
}
}
}
bool used[MAXN];
int dx[MAXN], dy[MAXN];
int mx[MAXN], my[MAXN];
int DFS(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(!used[v] && dy[v] == dx[u] + 1)
{
used[v] = true;
if(my[v] == -1 || DFS(my[v]))
{
my[v] = u; mx[u] = v;
return 1;
}
}
}
return 0;
}
int kcase = 1;
void HK()
{
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
int ans = 0;
while(1)
{
bool flag = false;
memset(dx, 0, sizeof(dx));
memset(dy, 0, sizeof(dy));
queue<int> Q;
for(int i = 1; i <= oddnum; i++)
if(mx[i] == -1)
Q.push(i);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(!dy[v])
{
dy[v] = dx[u] + 1;
if(my[v] == -1)
flag = true;
else
{
dx[my[v]] = dx[u] + 1;
Q.push(my[v]);
}
}
}
}
if(!flag) break;
memset(used, false, sizeof(used));
for(int i = 1; i <= oddnum; i++)
if(mx[i] == -1)
ans += DFS(i);
}
printf("Case %d: %d\n", kcase++, n - ans);
}
int main()
{
getP();
getPsum();
int t;
scanf("%d", &t);
while(t--)
{
getMap();
HK();
}
return 0;
}
LightOj-1336Sigma Function
题目描述：
求和运算是一种有趣的操作，它来源于古希腊字母σ，现在我们来求一个数字的所有因子之和。例如σ(24)=1+2+3+4+6+8+12+24=60.对于小的数字求和是非常的简单，但是对于大数字求和就比较困难了。现在给你一个n，你需要求出有多少个[ 1 , n ]区间内的数字σ是偶数。
注：一个数字的σ指这个数的所有因子之和
求解：
(1)初看题面 ，直接求约数个数求和肯定不行 ，转而列出一个数的约数个数式子来观察性质
（2）可以发现
对于x = p1^a1*p2^a2*...*pn^an;
所以x的因子和 f(x)= （1+p1+p1^2+p1^3+...+p1^a1）*(1+p2+pc++2^2+...+p2^a2)*..*(1+pn+pn^2+...+pn^an);
因为偶数乘偶数是偶数，偶数乘奇数还是偶数，只有奇数乘奇数是奇数，所以我们让每一个小括号都是奇数。最后我们减去奇数项就只剩偶数项了
（3） 显然当x只有2这一个素因子时，再加上一个1一定是奇数。
其次素数中只有2这一个偶数，所以其他素数都是奇数，偶数个奇数想加就是偶数，再加一个1就又会变成偶数，所以p ^ a(a是偶数）x^2的每一个p ^ a（a一定会是偶数，因为是两个x相乘，所以就是两个a相加，不管是奇数加奇数，还是偶数 加 偶数都会是 偶数）
（4）x ^ 2因子和是偶数了，那么2 * x ^ 2的因子和也是偶数。因为最后会加上一个 1 还是 奇数。
至此可以发现 我们的答案只需要减去2 ^ x , x ^ 2 和 2 * x ^ 2
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long int LL;
int main(){
int T, cas = 1;
cin >> T;
while(T --){
LL n;
cin >> n;
LL sum = n;
sum -= (int)sqrt(n);
sum -= (int)sqrt(n/2);
printf("Case %d: %lld\n", cas++, sum);
}
return 0;
}
LightOj-1382Leading and Trailing
题目描述：
给定两个数n,k 求n^k的前三位和最后三位
求解：
（1）后三位快速幂求即可 ，难点是前面三位的求法 ，数字非常大 ，高精度属实难操作
（2）（巧妙的推导）我们先假设n ^ k =a . bc * 10 ^ m。（因为是n的k次 ，这里就要往log上面思考了！）
方程两边同时对10求log，得到k * log10( n ) = m + log 10 (a.bc)。
减去前面的整数部分，再求10 ^ log 10（a.bc）最后在*100 ，
就可以得出需要的abc了 ，这题思维跳跃性很大 ，着实难想。
细节：
前三位可能不足三位记得补0 ，不然wa死wa死
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000;
typedef long long LL;
LL qmi(LL a,LL b){
LL ans=1;
while(b){
if(b & 1) ans = (ans * a) % mod;
a=( (a % mod) * (a % mod) ) % mod;
b >>= 1;
}
return ans % mod;
}
int main(){
int t;
cin >> t;
int cas = 1;
while(t--){
LL n,k;
cin >> n >> k;
LL res = qmi(n,k);
LL ans1 = res , ans2 = 0;
double q = k * log10( n ) - (int)(k * log10(n));
q = pow(10 , q);
ans2 = q * 100;
printf("Case %d: %lld %03lld\n",cas++,ans2,ans1);//这里注意前三位可能不足三位 ，需要补前导0
}
return 0;
}
LightOj1259Goldbach`s Conjecture
题目描述：
T组询问，每组询问是一个偶数n
验证哥德巴赫猜想
回答n=a+b
且a，b(a<=b)是质数的方案个数
求解：
（1）哥德巴赫猜想的问题一般都是与筛素数有关 ，直接掏出线性筛 ，对于一个质数a直接检查 n - a是不是质数即可
细节：
筛质数要筛到1e7 ，但是存质数数组可别开太大
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
const int N = 1e7 + 10 , M = 1e6 + 10;
bool st[N];
int cnt;
int primes[M];
void init(int n){
cnt = 0;
st[0] = st[1] = true;
// primes[cnt++] = 0;
// primes[cnt++] = 1;
for(int i = 2; i <= n; i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; primes[j] * i <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
int main(){
init(N);
int T,cas = 1;
cin >> T;
while(T--){
int n;
scanf("%d",&n);
int ans = 0;
for(int i = 0; i < cnt && primes[i] <= n/2; i++) if(!st[n - primes[i]] ) ans++;
printf("Case %d: %d\n",cas++,ans);
}
return 0;
}
LightOj-1245Harmonic Number
题目描述：
long long H( int n ) {
long long res = 0;
for( int i = 1; i <= n; i++ )
res = res + n / i;
return res;
}
给定代码 ，让你求值
求解：
（1）n最大为int的范围 ，暴力是肯定不行了 ，左看看右看看 ，只能列式子出来 ，试图找找性质和规律了。
（2）令n = 10 ，我们列出式子：
1：10/1-10/2；
2：10/2-10/3；
3：10/3-10/4；
4：10/4-10/5；
5：10/5-10-6；
6：10/6-10/7；
7：10/7-10/8；
8：10/8-10/9；
9：10/9-10-10；
10：10/10-10/11；
（3）通过观察，我们发现sqrt(n)到n之间肯定小于sqrt(n)，那么我们根据上面的那个式子可以算出商为i，[1<=i<=sqrt(n)]的个数，然后乘以i，就是sqrt(n)之后的贡献，然后在循环计算的过程中，我们可以轻松算出前sqrt(n)项的n / i值。求和即为答案
（4）如果n / i = i，那么i算了两遍。我们需要减去重复的。
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
const int N = 4e6 + 10;
typedef long long ll;
int main(){
ll n,m;
int T,cas=1;
cin >> T;
while(T--){
cin >> n;
ll ans = 0;
for(int i = 1;i <= sqrt(n) ; i ++){
ans += n / i;
ans += (n / i - n / (i + 1)) * i;
if(n / i == i) ans -= n / i;
}
printf("Case %d: %lld\n",cas++,ans);
}
return 0;
}
LightOj-1236Pairs Forming LCM
题目描述：
给定n ， 求满足lcm(a, b) == n， a <= b 的 (a,b)数对 的个数
求解：
（1）最小公倍数了 ，那基本就是要往约数上面靠了 ，掏出约数的几个性质往上面贴。
（2）约数个数好像可以 ，容易知道 n 是a, b的所有素因子取在a, b中较大指数的积
如果 N = p1^c1 * p2^c2 * ... *pk^ckc++
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
那么对于每个素因子pi ， pi在a,b中的指数ai, bi 至少有一个等于pi， 另一个小于等于pi（key）
（3）先不考虑a, b的大小 对于每个素因子pi分类讨论：
-
在a中的指数 ai == ei 那么 pi 在 b 中的指数就有 ei + 1 种情况（[0, ei] 中的所有数 ）
-
在a中的指数 ai < ei ，那么 pi 在 b 中的指数只能有 ei 种情况（ai 在属于[0, ei)）
（4） 总结一下：对于每个素因子都有 2 * ei + 1种 ，但是（n , n）只有一次 ，求出素因子出现的个数 ， 最后还要加上i = j 的(个数 + 1) / 2 ， 就是答案。
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
const int N = 1e7 + 5 , M = 1e6 + 10;
int primes[M], cnt;
bool st[N];
void init(){
cnt = 0;
for(int i = 2; i < N; i++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; j < cnt && primes[j] * i < N; j++){
st[primes[j] * i] = 1;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
init();
ll n, ans, sum;
int T, cas = 1;
cin >> T;
while(T--){
scanf("%lld", &n);
ans = 1;
for(int i = 0; i < cnt; i++){
if(ll(primes[i]) * primes[i] > n) break;
sum = 0;
while( n % primes[i] == 0){
n /= primes[i];
sum++;
}
if(sum) ans *= sum * 2 + 1;
}
if(n > 1) ans *= 3;
printf("Case %d: %lld\n", cas++, ans / 2 + 1);
}
return 0;
}
LightOj-1234Harmonic Number
题目描述：
在数学中，第n个调和数是前n个非零自然数的倒数之和 ， 在这个问题中，给你一个数n，你应该求出 Hn
其中Hn = 1 + 1 / 2 + 1 / 3 + 1 / 4 + … + 1/ n;
求解：
（1）第一个想法 ，打表 ，很可惜 ，n给了1e8 ，数组开不下 ，（别的性质呢 ，不太会…）。
（2）关于调和级数的求法 ，1.欧拉给出了一个近似公式 ， 2.分段打表 ，大概先算出n在哪一块 ，再打表。
1：公式：f(n)=ln(n)+C+1/(2*n)， 公式中C≈0.57721566490153286060651209;
但是使用的时候n必须大于1e4， 所以就打1e4的表 ，剩下的就是公式计算了。
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
const int N = 1e4 + 10;
using namespace std;
double a[N];
int main(){
a[1] = 1.0;
for(int i=2;i<=10000;i++) a[i] = a[i - 1] + 1.0 / i;
int T;
cin >> T;
int cas = 1;
while(T--){
int n;
cin >> n;
if(n <= 10000){c++
printf("Case %d: %.10lf\n" , cas++ , a[n]);
}
else{
double res = log(n) + 1.0 / (2 * n ) + 0.57721566490153286060651209;
printf("Case %d: %.10lf\n",cas ++,res);
}
}
return 0;
}
LightOj-1220Mysterious Bacteria
题目描述：
求满足条件的最大的指数p，使得a^p = x（a是整数）
求解：
（1）看到a的k次 ，要往唯一分解定理上靠了 ，即约数个数模板
如果 N = p1^c1 * p2^c2 * ... *pk^ckc++
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
（2）由于 x = p ^ k 中的 p 是确定的，因此可分解完所有指数，求 GCD(k1,k2,…,kn) 即可
细节：
x 可能为负数，如果 x 为负数的话说明k 必须是奇数 ， 如果解x是偶数的话，必须一直除二转换为奇数才行
质数筛到1e6即可 ，1e7会RE
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int primes[N],cnt;
bool st[N];
void init(){
cnt = 0;
for(int i = 2; i < N; i++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; j < cnt && primes[j] * i < N; j++){
st[primes[j] * i] = 1;
if(i % primes[j] == 0) break;
}
}
}
int GCD(int a, int b) {
return b?GCD(b,a%b):a;
}
int main() {
init();
int T;
cin >> T;
int cas = 1;
while(T--) {
LL x;
scanf("%lld",&x);
bool flag = false;
if(x < 0) x = -x , flag = true;
int res = 0;
for(int i = 0; (LL)primes[i] * primes[i] <= x && i < cnt ; i++) {
if(x % primes[i] == 0) {
int sum = 0;
while(x % primes[i]==0) {
sum++;
x/=primes[i];
}
if(res == 0) res = sum;
else res = GCD(res , sum);
}
}
if(x > 1) res = 1;
if(flag) while(res % 2 == 0) res /= 2;
printf("Case %d: %d\n" , cas ++ , res);
}
return 0;
}
LightOj-1214Large Division
题目描述：
给定两个整数a和b，你应该检查a是否可以被b整除。我们知道，当且仅当存在整数c使得a = b * c时，整数a才能被整数b整除。
求解：
（1）数字这么大直接除不行 ，用到大数取余 和 同余定理
（2）大数取模类似高精度算法 ，我们将以字符串输入，转化成整数的时候每次模b ，因为同余定理 ，保证了答案的正确性
细节：
如果数字是负数 ，直接转化成整数即可 ，因为符号与是否能整除没有关系
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
int main(){
int T,cas = 0;
cin >> T;
while(T--){
string a;
long long b;
cin >> a >> b;
if(b < 0) b = -b;
int i = 0;
while(a[i] == '-') i++;
long long res = 0;
for(; a[i]; i++) res = (res * 10 % b + a[i] - '0') % b;
if(!res) printf("Case %d: divisible\n",++cas);
else printf("Case %d: not divisible\n",++cas);
}
return 0;
}
LightOj-1213Fantasy of a Summation
题目描述：
给定一段代码 ，让你求和
#include <stdio.h>
int cases, caseno;
int n, K, MOD;
int A[1001];
int main() {
scanf("%d", &cases);
while( cases-- ) {
scanf("%d %d %d", &n, &K, &MOD);
int i, i1, i2, i3, ... , iK;
for( i = 0; i < n; i++ ) scanf("%d", &A[i]);
int res = 0;
for( i1 = 0; i1 < n; i1++ ) {
for( i2 = 0; i2 < n; i2++ ) {
for( i3 = 0; i3 < n; i3++ ) {
...
for( iK = 0; iK < n; iK++ ) {
res = ( res + A[i1] + A[i2] + ... + A[iK] ) % MOD;
}
...
}
}
}
printf("Case %d: %d\n", ++caseno, res);
}
return 0;
}
求解：
（1）看代码 ，初步觉得整个过程中加了n ^ k 次 ，仔细列了一下式子 ，发现其实每个元素被加的次数为n ^ (k - 1) * k
(2)次幂的问题直接掏出快速幂
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
ll qmi(int m, int k, int p){
ll res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
int main()
{
int T , cas = 1;
cin >> T;
while(T--){
int n,k,mod;
scanf("%d%d%d",&n,&k,&mod);
ll ans = 0;
for(int i = 0 ; i < n ; i ++){
int t;
scanf("%d",&t) , ans = (ans + t) % mod;
}
ll num = qmi(n,k-1,mod);
printf("Case %d: ",cas++);
printf("%d\n",(ans * num * k) % mod);
}
return 0;
}
LightOj-1197Help Hanzo
题目描述：
求区间[a , b] 之间有多少素数
求解：
（1）a, b 范围到int ， 直接筛是肯定不行的
（2）这里我们引入一个巧妙的区间筛法
（3）我们知道b以内的合数的最小质因数一定不会超过根号b，如果有根号b以内的素数表的话，就可以把埃式筛法运用在 [a,b)上了。
（4）我们先得出[ 2 , sqrt（b）)的表和 [ a , b ) 的 表 ，然后从[ a ,sqrt(b) )的表中筛得素数得同时，将其倍数从[a,b)得表中划去，最后剩下的就是区间[a,b)内的素数。
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
bool st[N],book[N];
ll qujian(ll a,ll b){
for(ll i = 0; i < sqrt(b); i ++) st[i] = true;
for(ll i = 0 ; i < b - a ; i ++) book[i] = true;
for(ll i = 2; i * i < b; i++){
if(st[i]){
for(ll j = 2 * i ; j * j < b; j += i) st[j] = false;
for(ll j = max(2ll , (a + i - 1 ) / i) * i ; j < b; j += i)book[j - a] = false;
}
}
ll sum = 0;
for(int i = 0; i < b - a; i ++)if(book[i]) sum++;
return sum;
}
int main(){
int T;
cin >> T;
int cas = 1;
while(T--){
ll a,b;
scanf("%lld%lld",&a,&b);
ll sum = qujian(a,b+1);
if(a==1)sum--;
printf("Case %d: %lld\n",cas++,sum);
}
return 0;
}
LightOj-1138Trailing Zeroes
题目描述：
n的阶乘尾部有q个连续的0，现在给你q，请你算出满足条件的n，如果有多个n满足条件，输出最小的那个即可。
求解：
（1）首先考虑到乘积得到0，是由若干2*5构成。
（2）问题就转化成找N！中有多少个2和5，
（3）再仔细想想2的个数一定比5多，那么我们只需要找到5即可
代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
const int INF = 0x3f3f3f3f;
using namespace std;
int check(int n){
int ans = 0;
while(n){
ans += n/5;
n = n/5;
}
return ans;
}
int main(){
int T, cas = 1 , n , num;
cin >> T;
while(T--){
cin >> n;
int l = 1, r = INF;
while(l < r){
int mid = (r + l) / 2;
if(check(mid) >= n) r = mid;
else l = mid + 1;
}
printf("Case %d: ", cas++);
num = check(l);
if(num == n) printf("%d\n", l);
else puts("impossible");
}
return 0;
}
tql，已三连