Acwing1292哥德巴赫猜想
如果暴力的枚举第一个数 ， 再检查n - 第一个数是否为素数 ，最坏情况时间复杂度为T组数据 * 1e6 * 根号（1e6） 约为1e9 * T会超时
正解：用线性筛法 ，筛1e6范围内的素数 。
时间复杂度为1e6 , 枚举第一个数可以从数组内第一个素数开始 ，第二个数是否满足要求为O1查询。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int primes[N] , n;
bool st[N];
void init(int n){
int cnt = 0;
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 - 1);
while(cin >> n && n){
for(int i = 1;; i ++){
int a = primes[i];
int b = n - a;
if(!st[b]){
printf("%d = %d + %d\n" , n , a , b);
break;
}
}
}
return 0;
}
Acwing1923夏洛克和他的女朋友
题目要求一个数如果是另一个数的质因子 ， 他们需要颜色不同
列出2 - 10来简单看一下
2 3 4 5 6 … 8 9 10
可以看到如果一个质数是另一个数的因子 ，那么我们需要染不同的颜色 ，类似从一个质数出发 ，往一个合数建一条边。
把质数和合数分开 ，可以发现每条边都是由一个质数指向另一个合数 ，所以其实只要染2种颜色就够了 。如果这个珠宝价值为质数 ，染成 1 ，如果珠宝价值为合数 染成2 ，这样就可以保证所有的价格里面质因子跟他的颜色不同。（cf的题藏得非常深）
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int primes[N];
bool st[N];
void init(int n){
int cnt = 0;
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(){
cin >> n;
init(n + 1);
if(n <= 2) cout << 1 <<endl;
else cout << 2 << endl;
for(int i = 2; i <= n + 1; i ++)
if(!st[i]) printf("1 ");
else printf("2 ");
return 0;
}
Acwing196质数距离
直接枚举L - R 之间的质数的话必须先筛1-R之间的质数，L ， R很大 ，无法处理。
正解：虽然L，R很大 ，但是R - L 只有1e6 ，因此可以考虑只筛R - L 之间的合数。
利用定理：任何一个合数n一定包含一个不超过N−−√N的质因子 ，这道题根号N大概是50000 ，所以筛50000以内的质数，然后用这个质数去筛掉[l,r]区间内的合数。
细节问题： 这里L 和 R 很大 ，数组下标开不下 ，我们要用到整体偏移的思想 ，筛的时候整个区间都左移L个 ，在下面计算的时候 再把L加上就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int primes[N] , cnt;
bool st[N];
void init(int n){
memset(st , 0 , sizeof st);
cnt = 0;
for(int i = 2; i <= n; i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; i * primes[j] <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
int main(){
ll l , r;
while( cin >> l >> r){
init(50000);
memset(st , 0 , sizeof st);
for(int i = 0; i < cnt; i ++){
ll p = primes[i];
for(ll j = ceil(l / p) * p ; j <= r; j += p) st[j - l] = true;
}
cnt = 0;
for(int i = 0; i <= r - l; i ++){
if(!st[i] && i + l >= 2) primes[cnt ++] = i + l;
}
if(cnt < 2) printf("There are no adjacent primes.\n");
else {
int minn = 0, maxn = 0;
for(int i = 0; i + 1 < cnt; i ++){
int del = primes[i + 1] - primes[i];
if(del < primes[minn + 1] - primes[minn]) minn = i;
if(del > primes[maxn + 1] - primes[maxn]) maxn = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n" , primes[minn],primes[minn + 1] , primes[maxn], primes[maxn + 1]);
}
}
return 0;
}
Acwing197 阶乘分解
首先n为1e6 ,直接算出1e6的阶乘显然不可能。
再考虑 ，因为是n的阶乘 ，需要枚举1到n的每个数 ，再把每个数分解 ，1e6 * 根号（1e6） 约为1e9 会超时。
正解：可以从反面来考虑 ，直接枚举n以内的每一个质数 ，n的阶乘中质数因子p的个数,就是1~n中每个数含有的质因数p的个数
至少有一个质因子p的有n / p个,而至少有两个质因子p数的有n / p ^ 2 ,以此类推 ，循环到p^k大于n为止。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int cnt ,primes[N];
bool st[N];
void init(int n){
for(int i = 2; i <= n; i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; i * primes[j] <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
int main(){
int n;
cin >> n;
init(n);
for(int i = 0; i < cnt; i ++){
int p = primes[i];
int sum = 0;
for(int j = n; j > 0; j /= p) sum += j / p;
printf("%d %d\n" , p ,sum);
}
return 0;
}
Acwing1289序列的第k个数
判断等差数列和等比数列 ： a , b , c 如果（a + c = 2 * b）是 等差数列
如果（a * c = b ^ 2）是 等比数列
易证得一个数列如果既是等差数列 ， 也是等比数列 ， 那么他一定是一个恒等数列 ， 即a = b = c.
等差数列第K项 ： a + (k - 1) * (b - a);
等比数列第K项 ： a * (b / a) ^ (k - 1);
因为a b c k为1e9 ， 所以乘幂操作需要快速幂提速。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 200907;
int qmi(int a ,int k){
int res = 1;
while(k){
if(k & 1) res = (ll)res * a % M;
a = (ll)a * a % M;
k >>= 1;
}
return res;
}
int main(){
int a , b , c, k , T;
cin >> T;
while(T--){
cin >> a >> b >> c >> k;
if(a + c == 2 * b) cout << a + (k - 1) * (ll) (b - a) % M << endl;
else cout << (ll) a * qmi(b / a , k - 1) % M << endl;
}
return 0;
}
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>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Maxn 1100000
using namespace std;
int T,n;
int phi[Maxn+1];
bool isPrime[Maxn+1];
int a[Maxn];
void Eular(){
for(int i = 1;i <= Maxn;i++) phi[i]=i;
memset(isPrime,true,sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
phi[1] = 0;
for(int i = 2;i <= Maxn;i ++){
if(isPrime[i]){
for(int j = i;j <= Maxn;j += i){
isPrime[j]=false;
phi[j] -= phi[j]/i;
}
}
}
}
int main(){
int Case=0;
Eular();
cin>>T;
while(T--)
{
MEM(a,0);
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 < Maxn;j++){
if(phi[j]>=a[i]){
sum+=j;
pos=j;
break;
}
}
}
printf("Case %d: %lld Xukha\n",++Case,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 <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 10;
int prime[MAXN];
int is_prime[MAXN];
int tot;
typedef long long LL;
void init(){
tot = 0;
is_prime[1]=1;
for(int i = 2;i < MAXN;i ++){
if(!is_prime[i]){
prime[tot ++] = i;
for(int j=i * 2;j < MAXN;j += i) is_prime[j] = 1;
}
}
}
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,b;
int t;
cin >> t;
int cas=1;
while(t--){
scanf("%lld%lld",&s,&b);
if(b * b >= s){
printf("Case %d: 0\n",cas++);
continue;
}
LL num = solve(s);
num /= 2;
for(LL i = 1;i < b;i++)
if(s % i == 0) num--;
printf("Case %d: %lld\n",cas++,num);
}
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;
}
