第十二周学习体会

第十二周学习体会

这个周学习了数论的有关内容，然后打了三场cf，主要的收获还是通过cf中看没做出来题目的题解，这三场打完基本上是处于掉分的状态，主要是因为对题意的理解时间太长，思路不清晰，然后就是对学过的知识运用不熟练。

下面是几条关于数论的知识：
费马小定理：
内容：
若存在整数 a , p 且gcd(a,p)=1,即二者互为质数，则有a^(p-1)≡ 1(mod p)。(这里的 ≡ 指的是恒等于，a^(p-1)≡ 1(mod p)是指a的p-1次幂取模与1取模恒等)

欧拉函数φ

 欧拉定理是用来阐述素数模下，指数同余的性质。欧拉定理：对于正整数N，代表小于等于N的与N互质的数的个数，记作φ(N)例如φ(8)=4，因为与8互质且小于等于8的正整数有4个，它们是：1,3,5,7欧拉定理还有几个引理，具体如下：①：如果n为某一个素数p，则φ(p)=p-1;①很好证明：因为素数p的质因数只有1和它本身，p和p不为互质，所以φ(p)=p-1；②：如果n为某一个素数p的幂次，那么φ(p^a)=(p-1)*p^(a-1)；②因为比p^a小的数有p^a-1个，那么有p^(a-1)-1个数能被p所整除（因为把1~p^a-1的p的倍数都筛去了）所以φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)③：如果n为任意两个数a和b的积，那么φ(a*b)=φ(a)*φ(b)③因为比a*b小的数有a*b-1个，条件是a与b互质那么可以知道，只有那些既满足a与其互质且既满足b与其互质的数满足条件。根据乘法原理，这样的数可以互相组合，那么就有φ(a)*φ(b)个所以可以得知φ(a*b)=φ(a)*φ(b) (注意条件必须满足a和b互质)

④：设n=(p1^a1)*(p2a2)……(pk^ak) (为N的分解式)

     那么φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)

④因为各个分解完的p1、p2、……pk均为素数，所以它们均为互质的

  每次再刨去它们本身，乘起来剩下的运用容斥原理，再根据引理②和引理③就可以得出欧拉定理：a^(φ(m))同余1(mod m) (a与m互质)

裴蜀定理
在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：

ax + by = m

有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。

题目：
1.
Let’s define the following recurrence:
an+1=an+minDigit(an)⋅maxDigit(an).
Here minDigit(x) and maxDigit(x) are the minimal and maximal digits in the decimal representation of x without leading zeroes. For examples refer to notes.

Your task is calculate aK for given a1 and K.

Input
The first line contains one integer t (1≤t≤1000) — the number of independent test cases.

Each test case consists of a single line containing two integers a1 and K (1≤a1≤1018, 1≤K≤1016) separated by a space.

Output
For each test case print one integer aK on a separate line.

Example
inputCopy
8
1 4
487 1
487 2
487 3
487 4
487 5
487 6
487 7
outputCopy
42
487
519
528
544
564
588
628
Note
a1=487

a2=a1+minDigit(a1)⋅maxDigit(a1)=487+min(4,8,7)⋅max(4,8,7)=487+4⋅8=519

a3=a2+minDigit(a2)⋅maxDigit(a2)=519+min(5,1,9)⋅max(5,1,9)=519+1⋅9=528

a4=a3+minDigit(a3)⋅maxDigit(a3)=528+min(5,2,8)⋅max(5,2,8)=528+2⋅8=544

a5=a4+minDigit(a4)⋅maxDigit(a4)=544+min(5,4,4)⋅max(5,4,4)=544+4⋅5=564

a6=a5+minDigit(a5)⋅maxDigit(a5)=564+min(5,6,4)⋅max(5,6,4)=564+4⋅6=588

a7=a6+minDigit(a6)⋅maxDigit(a6)=588+min(5,8,8)⋅max(5,8,8)=588+5⋅8=628

这道题本来是一道很简单的题，但是我想的太过复杂导致这道题做了一个小时还是没有ac。这道题只需要通过三个函数，第一个求出ai+1的每一位最小值，然后第二个求出每一位最大值，最后一个函数求出他的乘积就可以轻松解决。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 18
const int M=1e8;
int a[M],b[N];
bool cmp(int a,int b)
{return a<b;
}
int main()
{int t;cin>>t;while(t--){long long int k;memset(a,0,sizeof(a));memset(b,0,sizeof(b));cin>>a[1]>>k;for(int i=1;i<=k;i++){int cnt=a[i];int num=0;for(int j=1;cnt!=0;j++){int n=cnt;cnt=cnt/10;b[j]=n-cnt*10;num++;}sort(b+1,b+1+num,cmp);a[i+1]=a[i]+b[1]*b[num];}cout<<a[k]<<endl;}return 0;
}

这是我第一次提交的代码超时了，于是我输入了一些数据本来找到的规律是不管输入的数是多少，只要循环超过20次必定会出现最小值为0，所以从出现0往后的输出就不在发生变化，于是我把代码改成这样：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int ans,a[25],b[25];
bool cmp(int a,int b)
{return a<b;
}
int main()
{int t;cin>>t;while(t--){long long int k;memset(a,0,sizeof(a));memset(b,0,sizeof(b));cin>>a[1]>>k;for(int i=1; i<=20; i++){int cnt=a[i];int num=0;for(int j=1; cnt!=0; j++){int n=cnt;cnt=cnt/10;b[j]=n-cnt*10;num++;}sort(b+1,b+1+num,cmp);a[i+1]=a[i]+b[1]*b[num];}if(k<=20)ans=a[k];elseans=a[20];cout<<ans<<endl;}return 0;
}

但是还是没有提交成功，可能是因为我输入的这些数据不具有普遍性，我感觉实在是想不出来了就开始做下面的题了，谁知道比赛结束之后查了题解原来这么简单，我心态崩了啊。。。

ac代码：

#include<stdio.h>
int fmax(int n)
{int res=n%10;while(n){if(res<n%10){res=n%10;}n=n/10;}return res;
}
int fmin(int n)
{int res=n%10;while(n){if(res>n%10){res=n%10;}n=n/10;}return res;
}
int fmn(int n)
{return n+fmax(n)*fmin(n);
}
int main()
{int t=0;scanf("%d",&t);while(t--){int a1,k=0;scanf("%d%d",&a1,&k);for(int i=1;i<k;i++){a1=fmn(a1);}printf("%dn",a1);}
}

You are given two integers n and m. You have to construct the array a of length n consisting of non-negative integers (i.e. integers greater than or equal to zero) such that the sum of elements of this array is exactly m and the value ∑i=1n−1|ai−ai+1| is the maximum possible. Recall that |x| is the absolute value of x.

In other words, you have to maximize the sum of absolute differences between adjacent (consecutive) elements. For example, if the array a=[1,3,2,5,5,0] then the value above for this array is |1−3|+|3−2|+|2−5|+|5−5|+|5−0|=2+1+3+0+5=11. Note that this example doesn’t show the optimal answer but it shows how the required value for some array is calculated.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The only line of the test case contains two integers n and m (1≤n,m≤109) — the length of the array and its sum correspondingly.

Output
For each test case, print the answer — the maximum possible value of ∑i=1n−1|ai−ai+1| for the array a consisting of n non-negative integers with the sum m.

Example
inputCopy
5
1 100
2 2
5 5
2 1000000000
1000000000 1000000000
outputCopy
0
2
10
1000000000
2000000000
Note
In the first test case of the example, the only possible array is [100] and the answer is obviously 0.

In the second test case of the example, one of the possible arrays is [2,0] and the answer is |2−0|=2.

In the third test case of the example, one of the possible arrays is [0,2,0,3,0] and the answer is |0−2|+|2−0|+|0−3|+|3−0|=10.

这道题本来也是很简单，因为我在第三种情况的时候一开始对输出没有进行总结导致这道题卡了近半个小时。

ac代码：

#include <iostream>
using namespace std;
int main()
{int t;long long int n,m,ans;cin>>t;while(t--){cin>>n>>m;if(n==1)ans=0;else if(n==2)ans=m;elseans=2*m;cout<<ans<<endl;}return 0;
}

You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:

Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;
Let this segment be [l;r]. If r−l+1 is odd (not divisible by 2) then assign (set) a[l+r2]:=i (where i is the number of the current action), otherwise (if r−l+1 is even) assign (set) a[l+r−12]:=i.
Consider the array a of length 5 (initially a=[0,0,0,0,0]). Then it changes as follows:

Firstly, we choose the segment [1;5] and assign a[3]:=1, so a becomes [0,0,1,0,0];
then we choose the segment [1;2] and assign a[1]:=2, so a becomes [2,0,1,0,0];
then we choose the segment [4;5] and assign a[4]:=3, so a becomes [2,0,1,3,0];
then we choose the segment [2;2] and assign a[2]:=4, so a becomes [2,4,1,3,0];
and at last we choose the segment [5;5] and assign a[5]:=5, so a becomes [2,4,1,3,5].
Your task is to find the array a of length n after performing all n actions. Note that the answer exists and unique.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1≤n≤2⋅105) — the length of a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105).

Output
For each test case, print the answer — the array a of length n after performing n actions described in the problem statement. Note that the answer exists and unique.

Example
inputCopy
6
1
2
3
4
5
6
outputCopy
1
1 2
2 1 3
3 1 2 4
2 4 1 3 5
3 4 1 5 2 6

这道题比赛的时候一直想的是用二分解决，结果9之前都分析成功但是到了第10个数据就不行了，第二天看题解的时候发现这道题可以用优先队列解决，实际上正解就是使用优先队列维护每段区间的最优性，每次二分后子区间入队，很轻松就求解了。

ac代码：

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;struct node{int l,r,len;bool operator < (const node& p) const {if(len==p.len) return l>=p.l;return len<p.len;}};priority_queue<node> p;int a[maxn];
int t,n;int main(){//freopen(&#","r",stdin);//freopen(&#","w",stdout);//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--){cin>>n;//while(!p.empty()) p.pop();p.push(node{1,n,n});int cnt=0;while(!p.empty()){node u&#p(); p.pop();int mid=(u.l+u.r)/2;a[mid]=++cnt;//cout<<u.l<<" "<<u.r<<endl;//cout<<cnt<<endl;if(u.l<=mid-1) p.push(node{u.l,mid-1,mid-u.l});if(mid+1<=u.r) p.push(node{mid+1,u.r,u.r-mid});}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;}return 0;
}

Orac is studying number theory, and he is interested in the properties of divisors.

For two positive integers a and b, a is a divisor of b if and only if there exists an integer c, such that a⋅c=b.

For n≥2, we will denote as f(n) the smallest positive divisor of n, except 1.

For example, f(7)=7,f(10)=2,f(35)=5.

For the fixed integer n, Orac decided to add f(n) to n.

For example, if he had an integer n=5, the new value of n will be equal to 10. And if he had an integer n=6, n will be changed to 8.

Orac loved it so much, so he decided to repeat this operation several times.

Now, for two positive integers n and k, Orac asked you to add f(n) to n exactly k times (note that n will change after each operation, so f(n) may change too) and tell him the final value of n.

For example, if Orac gives you n=5 and k=2, at first you should add f(5)=5 to n=5, so your new value of n will be equal to n=10, after that, you should add f(10)=2 to 10, so your new (and the final!) value of n will be equal to 12.

Orac may ask you these queries many times.

Input
The first line of the input is a single integer t (1≤t≤100): the number of times that Orac will ask you.

Each of the next t lines contains two positive integers n,k (2≤n≤106,1≤k≤109), corresponding to a query by Orac.

It is guaranteed that the total sum of n is at most 106.

Output
Print t lines, the i-th of them should contain the final value of n in the i-th query by Orac.

Example
inputCopy
3
5 1
8 2
3 4
outputCopy
10
12
12
Note
In the first query, n=5 and k=1. The divisors of 5 are 1 and 5, the smallest one except 1 is 5. Therefore, the only operation adds f(5)=5 to 5, and the result is 10.

In the second query, n=8 and k=2. The divisors of 8 are 1,2,4,8, where the smallest one except 1 is 2, then after one operation 8 turns into 8+(f(8)=2)=10. The divisors of 10 are 1,2,5,10, where the smallest one except 1 is 2, therefore the answer is 10+(f(10)=2)=12.

In the third query, n is changed as follows: 3→6→8→10→12.

这道题也是写的太复杂了，导致最后的超时，直接卡了快一个小时。实际上可以通过分类然后构造函数解决。

错误代码：

#include<iostream>
using namespace std;
int main()
{int t;cin>>t;while(t--){long long int n,k,m;cin>>n>>k;while(k--){m=n;for(long long int i=2;i*i<=n;i++){if(n%i==0){n+=i;break;}}if(m==n)n+=m;}cout<<n<<endl;}return 0;
}

ac代码：

#include<iostream>
#include<cmath>
using namespace std;
int solve(int x)
{int ans,cnt=1;for(int i=3; i<=sqrt(x); i++){if(x%i==0){ans=i;cnt=0;break;}i++;}if(cnt==1)ans=x;return ans;
}
int main()
{int t,n,k;cin>>t;while(t--){cin>>n>>k;if(k==1)cout<<n+solve(n)<<endl;else if(n%2==0){cout<<n+2*k<<endl;}else{cout<<n+solve(n)+2*(k-1)<<endl;}}return 0;
}

生死看淡，不服就干