「kuangbin带你飞」专题十四 数论基础

Diposting di | Edited on

传送门

A - Bi-shoe and Phi-shoe(欧拉函数的性质)

题意

给出一些数字，对于每个数字找到一个欧拉函数值大于等于这个数的数，求找到的所有数的最小和。

思路

考察了欧拉函数的简单性质，即满足欧拉函数(k)>=N的最小数为N+1之后的第一个素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
vector<int>ppp;
void phi_table(int n){
    phi[1]=1;
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){prime[tot++]=i;phi[i]=i-1;ppp.push_back(i);}
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    phi_table(2000000);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int>ve;
        ll ans=0;
        for(int i=1;i<=n;i++){
            int a;
            cin>>a;
            ans+=ppp[lower_bound(ppp.begin(),ppp.end(),a+1)-ppp.begin()];
        }
        cout<<"Case "<<cnt++<<": "<<ans<<" Xukha"<<endl;
    }
    return 0;
}

C - Aladdin and the Flying Carpet（唯一分解定理）

题意

给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b

思路

唯一分解定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
void phi_table(int n){
    phi[1]=1;
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){prime[tot++]=i;phi[i]=i-1;}
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
ll getnum(ll n){
    ll ans=1,num=0;
    for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            num=0;
            while(n%prime[i]==0){
                n/=prime[i];
                num++;
            }
            ans*=(num+1);
        }
    }
    if(n>1)ans*=2;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    phi_table(1000000+50);
    while(t--){
        ll a,b;
        cin>>a>>b;
        if(a<=b*b){
            cout<<"Case "<<cnt++<<": ";
            cout<<0<<endl;
            continue;
        }
        ll ans=getnum(a)/2;
        for(ll i=1;i<b;i++){
            if(a%i==0)ans--;
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

D - Sigma Function （平方数和平方数×2的约数和是奇数 ）

题意

求1-n中的因子和为偶数的个数是多少

思路

平方数和平方数*2的约数和是奇数

而且——-平方数*2的个数就等于sqrt（n/2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        ll ans;
        cin>>ans;
        ans-=floor(sqrt(ans))+floor(sqrt(ans/2));
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

E - Leading and Trailing(求 n^k 前3项和后3项)

思路

后三项不需要想就知道是快速幂了

但是前三项需要推一下

我们知道任意数可以转化成 X = 10^( x + y ) (x为整数，y为小数)

其中 10^x 来控制的是源数字 10 100.。。这样的东西，而具体这个数字等于多少，全靠10^y ，

那么 我们就可知道 10^y 就是我们要求的前n个数字还不会炸 long long (用double的话末尾消去，很适合)

这样我们就能保证前7位可知， 如果要前三位 只需要 10^(y) * 100 就好了。

由于这道题数据卡的不是太死。。限时 2s ，那么不用快速幂去搞前三位。。似乎没事。

fmod 是一个特殊函数 fmod(a,b) (a , b 为 浮点型) 得出的结果是 a / b 得出的结果的小数。。

距离 fmod( 4, 3 ) 结果为 0.3333333 ，那么我们这样 fmod( x , 1 ) 就是默认取他的小数点位

那么 对于 X^k = 10^x * 10^y

x + y = k lg X ,那么 y = fmod( klg X, 1.0 )

然后再*100就是前三位了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int pow_mod(int x,int n,int mod){
    int res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main()
{
    /*std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int ans1=pow(10.0,fmod(k*log10(n*1.0),1))*100;
        int ans2=pow_mod(n%1000,k,1000);
        printf("Case %d: %03d %03d\n",cnt++,ans1,ans2);
    }
    return 0;
}

F - Goldbach`s Conjecture (线性筛)

题意

T组询问，每组询问是一个偶数n
验证哥德巴赫猜想
回答n=a+b
且a，b(a<=b)是质数的方案个数

思路

注意不要被卡内存就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int prime[700000];
int tot;
void getprime(){
    tot=0;
    for(int i=2;i<maxn;i++){
        if(!check[i]){
            prime[tot++]=i;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>=maxn)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    getprime();
    while(t--){
        int n;
        cin>>n;
        int ans=0;
        for(int i=0;i<tot&&prime[i]*2<=n;i++){
            if(!check[n-prime[i]])ans++;
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

G - Harmonic Number (II)（整除分块）

题意

求f(n)=n/1+n/2…..n/n,其中n/i保留整数;

思路

直接套莫比乌斯反演的整除分块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll ans=0;
        for(ll l=1,r;l<=n;l=r+1){
            r=n/(n/l);
            ans+=(r-l+1)*(n/l);
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

H - Pairs Forming LCM (唯一分解定理)

题意

求有多少组 （ i，j ）
使 lcm(i, j) = n and (i ≤ j).
(1 ≤ n ≤ 10^14)

思路

图片来源

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int prime[1000000];
int tot;
void getprime(){
    tot=0;
    for(int i=2;i<maxn;i++){
        if(!check[i]){
            prime[tot++]=i;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>=maxn)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
ll getnum(ll n){
    ll ans,sum;
    ans=0;
    sum=1;
    for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            ans=0;
            while(n%prime[i]==0){
                n/=prime[i];
                ans++;
            }
            sum*=(2*ans+1);
        }
    }
    if(n>1)sum*=3;
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    getprime();
    while(t--){
        ll n;
        cin>>n;
        cout<<"Case "<<cnt++<<": ";
        cout<<getnum(n)/2+1<<endl;
    }
    return 0;
}

I - Harmonic Number (欧拉常数 /稀疏打表求调和级数)

题意

t组数据，每组一个n 求 1+1/2+1/3+1/4 ……+1/n的和

思路

直接100个一组打表求前1e7项

或者直接套公式

r=0.57721566490153286060651209（r就是欧拉常数）。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
double num[maxn];
void init(){
    num[0]=0;
    num[1]=1.0;
    double ans=1.0;
    for(int i=2;i<=100000000;i++){
        ans+=1.0/(i*1.0);
        if(i%100==0)num[i/100]=ans;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    init();
    while(t--){
        int n;
        cin>>n;
        int k=n/100;
        double ans=num[k];
        for(int i=k*100+1;i<=n;i++)ans+=1.0/(i*1.0);
        cout<<"Case "<<cnt++<<": ";
        cout<<fixed<<setprecision(10);
        cout<<ans<<endl;
    }
    return 0;
}

J - Mysterious Bacteria (唯一分解定理，有符号整数只有31位，负数指数只能是奇数)

题意

给你一个整数n(可能为负数),让你求满足a^p=n的最大的p

思路

当n是正数时,直接对n进行素因子分解，在对它的素因子的个数进行gcd,比如12=2^2*3,gcd(2,1)就是最大的p;

当n是负数时,则p的值一定是奇数,因为一个数的偶数次方一定为整数，因此需要将它的素因子个数全都化为奇数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
ll factor[100][2];
int fatcnt;
int getfactors(ll x){
    fatcnt=0;
    ll tmp=x;
    for(int i=1;i<=prime[0]&&prime[i]<=tmp/prime[i];i++){
        factor[fatcnt][1]=0;
        if(tmp%prime[i]==0){
            factor[fatcnt][0]=prime[i];
            while(tmp%prime[i]==0){
                factor[fatcnt][1]++;
                tmp/=prime[i];
            }
            fatcnt++;
        }
    }
    if(tmp!=1){
        factor[fatcnt][0]=tmp;
        factor[fatcnt++][1]=1;
    }
    return fatcnt;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    getprime();
    while(t--){
        ll n;
        cin>>n;
        bool flag=0;
        if(n<0){
            flag=1;n=-n;
        }
        int tot=getfactors(n);
        ll gc=factor[0][1];
        for(int i=0;i<tot;i++){
            gc=__gcd(gc,factor[i][1]);
        }
        if(flag){
            while(gc%2==0)gc/=2;
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<gc<<endl;
    }
    return 0;
}

K - Large Division (同余模定理)

题意

给你一个大数A问你是否可以被一个b整除

思路

直接同余模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;

    while(t--){
        string a;ll b;
        cin>>a>>b;
        ll ans=0;
        if(b<0)b=-b;
        int len=a.length();
        for(int i=0;i<len;i++){
            if(a[i]=='-')continue;
            ans=(ans*10+a[i]-'0')%b;
        }
        cout<<"Case "<<cnt++<<": ";
        if(ans==0)cout<<"divisible"<<endl;
        else
            cout<<"not divisible"<<endl;
    }
    return 0;
}

L - Fantasy of a Summation（快速幂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll a[maxn];
ll pow_mod(ll a,ll n,ll mod){
    ll res=1;
    while(n){
        if(n&1)res=(res*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return res;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        int n;ll ans=0,mo,k;
        cin>>n>>k>>mo;
        for(int i=1;i<=n;i++)cin>>a[i],ans=(ans+a[i])%mo;
        cout<<"Case "<<cnt++<<": ";
        cout<<(ans*(pow_mod(n,k-1,mo)*k)%mo)%mo<<endl;
    }
    return 0;
}

M - Help Hanzo (大区间素数筛选)

题意

给出T个实例，T<=200，给出[a,b]区间,问这个区间里面有多少个素数？(1 ≤ a ≤ b < 231, b - a ≤ 100000)

思路

首先先把筛素数改成筛非素数

然后先用sqrt(b)里面的素数去筛a-b之间的非素数 剩下的就都是素数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
bool flag[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    getprime();
    while(t--){
        ll a,b;
        cin>>a>>b;
        memset(flag,0,sizeof(flag));
        int dis=b-a;

        for(int i=1;i<=prime[0]&&prime[i]*prime[i]<=b;i++){
            for(int j=a/prime[i]*prime[i];j<=b;j+=prime[i])
            if(j>=a&&j>prime[i])flag[j-a]=true;

        }
        ll ans=0;
        for(int i=0;i<=dis;i++)
            if(!flag[i])ans++;
        if(a==1)ans--;
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

N - Trailing Zeroes (III) （二分）

题意

N！后面有Q个0，给你Q,求N

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e9+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int check(int mid){
    int k=0;
    while(mid){
        k+=mid/5;
        mid/=5;
    }
    return k;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;

    while(t--){
        int q;
        cin>>q;
        int l=-1,r=maxn,ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            int k=check(mid);
            if(k==q){
                ans=mid;
                r=mid-1;
            }
            else if(k<q){
                l=mid+1;
            }
            else if(k>q){
                r=mid-1;
            }
        }
        cout<<"Case "<<cnt++<<": ";
        if(ans==-1)cout<<"impossible"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

O - GCD - Extreme (II) （欧拉函数的应用）

题意

求sum(gcd(i,j),1<=i<j<=n)1<n<4000000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=4e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
ll phi[maxn];
int prime[maxn];
int tot;
ll sum[maxn];
void phi_table(int n){
    phi[1]=0;
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){prime[tot++]=i;phi[i]=i-1;}
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<=n;i++){
        phi[i]+=phi[i-1];
        sum[i]+=sum[i-1]+i;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    phi_table(4000000);
    int n;
    while(cin>>n&&n){
        ll ans=0;
        for(int l=1,r;l<=n;l=r+1){
            r=n/(n/l);
            ans+=phi[(n/l)]*(sum[r]-sum[l-1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

R - 青蛙的约会 (exgcd)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=4e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
///返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(a==0&&b==0)return -1;
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll xx,yy,m,n,l;
    cin>>xx>>yy>>m>>n>>l;
    ll a=(m-n);
    ll b=l;
    ll c=yy-xx;
    ll x,y;
    ll d=extend_gcd(a,b,x,y);
    if(c%d){
        cout<<"Impossible"<<endl;
    }
    else{
        x*=(c/d);
        x=(x%l+l)%l;
        cout<<x<<endl;
    }
    return 0;
}

S - C Looooops (exgcd)

思路

满足下列方程

ax0+by0=gcd(a,b);

如果c%gcd==0 那么此方程有解，否则没有解

若有解

方程两边同时乘以 c/gcd(a,b) 得 (a×c/gcd(a,b))×x0+(bc/gcd(a,b))y0=c;

这时得出方程的一个解 x1=x0×c/gcd(a,b) y1=y0×c/gcd(a,b)

求最小整数解 意思把x1变到减少到不能减少为止 也就是把x0 减少到不能减少为止

若x0减小x，那么方程左边 整体会减少 （ac/gcd(a,b)）x 此时 y0 需要增加相应的数使得等式平衡

而假设 y0增加了y 总体增加了 （bc/gcd(a,b)）y 此时 （ac/gcd(a,b)）x==(ac/gcd(a,b))y

而且x,y为整数 我们可以得到 x/y==b/gcd(a,b) / a/gcd(a,b)

这时 x每次减少 b/gcd(a,b) y只需增加 a/gcd(a,b) 就可以使得等式平衡。 那为什么我们不约掉gcd(a,b)?

因为x越小，我们得到的最小整数解就会越小。。。。

这时我们让x0不断减 x (x=b/gcd(a,b)) 直到 x0-ix>=0 && x0-(i+1)x<0 (i为减x的次数) 这时得到的就是最小整数解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=4e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
///返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(a==0&&b==0)return -1;
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll aa,bb,cc,kk;
    while(cin>>aa>>bb>>cc>>kk){
        if(aa==0&&bb==0&&cc==0&&kk==0)break;
        ll a=cc;
        ll b=1LL<<kk;
        ll c=bb-aa;
        ll x,y;
        ll d=extend_gcd(a,b,x,y);
        if(c%d){
            cout<<"FOREVER"<<endl;
        }
        else{
            ll x0=x*(c/d)%b; ///变成特解
            cout<<(x0%(b/d)+(b/d))%(b/d)<<endl;
        }
    }
    return 0;
}

U - Primes （水）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int prime[maxn];
void init(){
    check[1]=true;
    for(int i=2;i<maxn;i++){
        if(!check[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]*i<maxn;j++){
            check[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
    check[2]=true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    int tot=1;
    init();
    while(cin>>n&&(n>0)){
        cout<<tot++<<": ";
        if(check[n]){
            cout<<"no"<<endl;
        }
        else cout<<"yes"<<endl;
    }
    return 0;
}

X - Farey Sequence (欧拉函数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
ll sum[maxn];
void phi_table(int n){
    phi[1]=1;
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){prime[tot++]=i;phi[i]=i-1;}
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=2;i<=n;i++){
        sum[i]=sum[i-1]+phi[i];
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    int tot=1;
    phi_table(maxn-1);
    while(cin>>n&&(n>0)){
        cout<<sum[n]<<endl;
    }
    return 0;
}