数论专题整理(1)

acm

数论专题整理

A - Bi-shoe and Phi-shoe

Ａ打表题。

题意是找到最小的i使得$\phi(i)$大于所给值。并求取所有这样的i的$\sum{i}$和。

$\phi(i)$最小的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
29
30
31
32
33
34
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1000000;
int prime[maxn/10],sgn[maxn+7],cnt;

void initial(){
    for(int i = 2; i < maxn + 7; i++){
        if(!sgn[i]){
            prime[cnt++] = i;
            for(int j = i+i; j < maxn +7; j+=i){
                sgn[j] = 1;
            }
        }
    }
}

int main(){
    initial();
    int t;
    cin>>t;
    for(int i=1; i<=t;i++){
        int n,x;
        cin>>n;
        long long ans=0;
        for(int j=0; j<n; j++){
            cin>>x;
            ans+=prime[lower_bound(prime,prime+cnt,x+1)-prime];
        }
        printf("Case %d: %lld Xukha\n",i,ans);
    }
    return 0;
}

C - Aladdin and the Flying Carpet

Ｃ题是看一个数Ａ有多少大于b的因数对。由于数字较大，暴力肯定超时。采取Ａ的标准素因数分解式通过除数函数计算因数个数。

$\tau(a) =\prod{(\alpha_i+1)}$.

对于b的话，暴力跑一下就可以，如果大于$A^{\frac{1}{2}}$就是０。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#define CLR(a,v) memset(a,v,sizeof a)
using namespace std;
const int maxn = 1000005;
typedef long long ll;

bitset<maxn> vis;
int prime[maxn/10];
int p;
inline ll in()
{
    ll res=0;char c;
    while((c=getchar())<'0' || c>'9');
    while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
    return res;
}

void getPrime(){
    for(int i = 2; i< maxn; i++){
        if(!vis[i]){
            prime[p++]=i;
            for(int j = i+ i; j < maxn; j+=i){
                vis[j] = 1;
            }
        }
    }
}

int main(){
    getPrime();
    int T =in(),t=0;
    while(t++<T){
        ll area = in(),min = in();
        if(min>=sqrt(area)){
            printf("Case %d: %d\n",t,0);
            continue;
        }
        ll tmp = area;
        int ans = 1;
        for(int i = 0; 1LL*prime[i]*prime[i]<=area;i++){
            int cnt = 0;
            while(area%prime[i] == 0){
                cnt++;
                area/=prime[i];
            }
            ans*=(cnt+1);
        }
        if(area==1)ans>>=1;
        for(int i = 1; i< min; i++)if(tmp%i==0)ans--;
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}

D - Sigma Function

Ｄ题是关于除数和函数的一道题目。问的是１－n中有多少除数和函数$\delta(i)$值为偶数。据观察p=2或者奇数。p=2时显然那个数为奇数，p=奇数时，只要$e_i$是奇数即可。

从反面考虑即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
/*
σ(x)为偶数，只要存在因子pi^(ei+1)−1／(pi−1)为偶数即成立；
即x存在素因子为奇数次；
(1)t=p2≤n, 即t的因子都为偶数次;
(2)t=2∗q2≤n;
∵2ei+1−12−1=2∗p,2ei+1=2∗p+1; 恒不成立，即因子2的个数不影响结果，排除2为奇数个的情况；

*/
int main(){
    int t=0,T;scanf("%d",&T);
    while(t++<T){
        ll n;
        scanf("%lld",&n);
        ll ans = (int)sqrt(n)+(int)sqrt(n/2.0);
        printf("Case %d: %lld\n",t,n-ans);
    }
    return 0;
}

E - Leading and Trailing

Ｅ题是给出一个n,k，求取$n^k$的前三位数字和末三位数字。前三位数字用qlog(n,k)求解。通过log得到如科学计数法的形式a*10^k,而a就是10^(小数部分)。末三位只要快速幂mod一下就可以了。如果$n^k$<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
34
35
36
37
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
typedef long long ll;
using namespace std;

int qmod(long long n , long long k){
    ll res = 1;
    while(k>0){
        if(k&1)res=(res*n)%1000;
        n = (n*n)% 1000;
        k >>= 1;
    }
    return res%1000;
}

int qlog(long long n, long long k){
    double a = log10(n+0.0)*k;
    if(a<=3)return pow(10,a);
    a-=(ll) a;
    int ans = pow(10.0,a)*1000;
    while(ans>=1000){ans/=10;}
    return ans;
}

int main(){
    int T,t=0;
    scanf("%d",&T);
    ll n,k;
    while(t++<T){
        scanf("%lld%lld",&n,&k);
        printf("Case %d: %03d %03d\n",t,qlog(n,k),qmod(n,k));
    }
    return 0;
}

F - Goldbach`s Conjecture

Ｆ题给出一个偶数n，看有多少对数(a,b)满足1.a+b=n,2.a$\le$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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
#define maxn 10000005
using namespace std;
bitset<maxn> a;
int prime[maxn/10];
int cont=0;

inline void getPrime(){
    for(int i = 2; i< maxn; i++){
        if(!a[i]){
            prime[cont++] = i;
            for(int j = i+i; j < maxn ; j+=i)
                a[j] = 1;
        }
    }
}

int main(){
    getPrime();
    int T,t=0;
    scanf("%d",&T);
    int ans;
    while(t++<T){
        ans=0;
        int n;scanf("%d",&n);
        for(int i = 0;prime[i]<=n/2;i++){
            if(!a[n-prime[i]])ans++;
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}

G - Harmonic Number (II)

Ｇ求$\sum_{1\le i \le n}\frac{n}{i}$

考虑对称性。对于i的值为$\frac{n}{i}$,相对称的就有$\frac{n}{i}-\frac{n}{i+1}$个值为i;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cmath>

using namespace std;

int main(){
    int t=0,T;
    scanf("%d",&T);
    while(t++<T){
        long long n;
        scanf("%lld",&n);
        int m = sqrt(n);
        long long ans = 0;
        for(int i = 1; i <=m; i++){
            ans+=n/i;//oneprat
            ans+=i*(n/i-n/(i+1));//anotheraprt
        }
        if(n/m==m)ans-=n/m;//ji
        printf("Case %d: %lld\n",t,ans);
    }
    return 0;
}

H - Pairs Forming LCM

H题就和上面的Ｃ题有点像。我们先假装把给的n做标准素因数分解。因为是lcm，所以考虑每个素因数p，有点像组合数学式的，把他分陪给两个人，两个人最大的是$p_i^{e_i}$.每个因数都是$2e_i + 1$种情况。乘起来。因为考虑的是(i,j)对，而且要满足$i \le j$，所以要除２．考虑到我们所求的是奇数。奇数奇在何处？也就是(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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
#define maxn 10000000
using namespace std;
bitset<maxn> a;
int prime[maxn/10];
int cont=0;

inline void getPrime(){
    for(int i = 2; i< maxn; i++){
        if(!a[i]){
            prime[cont++] = i;
            for(int j = i+i; j < maxn ; j+=i)
                a[j] = 1;
        }
    }
}
int main(){
    getPrime();
    int T,t=0;
    scanf("%d",&T);
    while(t++<T){
        long long n,ans = 1,m;
        scanf("%lld",&n);
        m = n;
        for(int i = 0; prime[i] <= m/prime[i] && i < cont-1; ++i){
            int cot = 0;
            while(m%prime[i]==0){
                cot++;
                m/=prime[i];
            }
            ans*=(cot*2+1);
        }
        if(m>1)ans*=3;
        ans = (ans+1)/2;
        printf("Case %d: %lld\n",t,ans);
    }
    return 0;
}

I - Harmonic Number

Ｉ 题就是求$\sum\frac{i}{n}$调和级数求和。可以开外挂，也可以打表。

打表是因为是ie8,按每５０个打表就可以了．

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
#include<cstdio>
#define maxn  1e8
using namespace std;
double a[(int)maxn/50+10];

void init(){
    a[0] = 0;
    for(int i = 0; i <= maxn/50+9; i++){
        double tmp = 0;
        for(int j = i*50+1; j <= i*50+50;j++){
            tmp+=1.0/j;
        }
        a[i+1] = a[i]+tmp;
    }
}

int main(){
    init();
    int t=0,T;
    scanf("%d",&T);
    while(t++<T){
        double ans = 0;
        int n;scanf("%d",&n);
        ans+=a[n/50];
        for(int i = n/50*50+1; i <= n; i++){
            ans+=1.0/i;
        }
        printf("Case %d: %.10f\n",t,ans);
    }
    return 0;
}

也可以开挂．用欧拉常数．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<cmath>
//oulachangshu:0.57721566490153286060651209
using namespace std;
double a[10010];
double r=0.57721566490153;
int main(){
    int n,i,cas=0,nn;
    for(int i=1;i<=10000;i++)
        a[i]=1.0/i+a[i-1];
    scanf("%d",&nn);
    while(cas++<nn){
        scanf("%d",&n);
        double i,ans=0;
        printf("Case %d: %.10f\n",cas,n>10000?1.0/(2*n)+log(n)+r:a[n]);
    }
}

J - Mysterious Bacteria

Ｊ题的题意是问一个数是$x^p$，求解p最大为多少．

仍然采用标准素因数分解．显然有$min(e_i)$｜$e_j$．

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
#define maxn 70000
#define CLR(a,v) memset(a,v,sizeof a)
using namespace std;
bitset<maxn> a;
int prime[maxn];
int cont=0;
int vis[maxn]={0};
inline void getPrime(){
    for(int i = 2; i< maxn; i++){
        if(!a[i]){
            prime[cont++] = i;
            for(int j = i+i; j < maxn ; j+=i)
                a[j] = 1;
        }
    }
}
int main(){
    getPrime();
    int T,t=0;
    scanf("%d",&T);
    while(t++<T){
        CLR(vis,0);
        long long n,ans = 1,m;
        scanf("%lld",&n);
        int flag2= 0;
        if(n<0){n=-n;flag2= 1;}
        m = n;
        int minx = 1000;
        int lu = 0;
        for(int i = 0; prime[i] <= m/prime[i] && i < cont-1; ++i){
            if(m%prime[i]!=0){continue;}
            while(m%prime[i]==0){
                m/=prime[i];
                vis[i]++;
            }
            lu = i;
            minx=min(vis[i],minx);
        }
        if(m>1){printf("Case %d: 1\n",t);continue;}
        int flag = 0;
        for(int i = 0; i<=lu;i++){
            if(vis[i]==0)continue;
            if(vis[i]%minx!=0){
                flag=1;
                break;
            }
        }
        if(flag)minx=1;
        if(flag2){
            while(minx%2==0){
                minx/=2;
            }
        }
        printf("Case %d: %lld\n",t,minx);
    }
    return 0;
}

K - Large Division

k题就是模拟一个大数除法．

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>

using namespace std;
char input[300];
long long b;
int main(){
    int t=0,T;
    scanf("%d",&T);
    while(t++<T){
        scanf("%s%lld",input,&b);
        if(b<0)b=-b;
        long long ans=0;
        int i=0;
        for(;input[i]<'0' || input[i]>'9';i++);
        for(;input[i]<='9' && input[i]>='0';i++){
            ans=ans*10+(input[i]-'0');
            ans%=b;
        }
        printf("Case %d: %sdivisible\n",t,(ans==0)?"":"not ");
    }
    return 0;
}

L - Fantasy of a Summation

L题首先手算一下,res = $kn^{k-1}\sum{a[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
29
30
31
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int mod,temp,n,k;
long long qpow(int n, int k){
    long long ans=1;
    while(k){
        if(k&1){ans=ans*n%mod;}
        n = n*n %mod;
        k>>=1;
    }
    return ans%mod;
}

int main(){
    int t=0,T;
    scanf("%d",&T);
    while(t++<T){
        long long sum=0;
        scanf("%d%d%d",&n,&k,&mod);
        for(int i = 0; i<n ; i++){
            scanf("%d",&temp);
            sum+=temp;
            sum%=mod;
        }
        sum*=k;
        printf("Case %d: %lld\n",t,(qpow(n,k-1)*sum)%mod);
    }
    return 0;
}

M - Help Hanzo

M 题是求解[a,b]区间内存在多少个质数．

考虑到欧拉筛．．．可是数据范围有些大，但题目中给了b-a$\le$100000.

可以考虑只筛选[a,b];先打一个质数表0-50000(>$2^{15.5}$)即可.

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
#include<cstdio>
using namespace std;
int pd[10000];
bool judge[50010] = {0};
void init(){
    for(int i = 2; i <= 500; i++){
        if(!judge[i]){
            for(int j = i*i; j <= 50000; j+=i){
                judge[j] = 1;
            }
        }
    }
    int j = 0;
    for(int i = 2; i<= 50000; i++){
        if(!judge[i])pd[j++]=i;
    }
}

long long get(long long a, long long b){
    long long sum = 0;
    bool sspd[200005]={0};
    if(a<2){a=2;}
    for(int i = 0; pd[i] <= b/pd[i]; i++){
        long long j = pd[i]*(a/pd[i]);
        if(j<a)j+=pd[i];
        if(j==pd[i])j+=(long long)pd[i];
        for(;j<=b; j+=pd[i])sspd[j-a]=1;
    }
    for(int i = 0; i < b-a+1; i++){
        if(!sspd[i])sum++;
    }
    return sum;
}

int main(){
    init();
    int t=0,T,a,b;
    scanf("%d",&T);
    while(t++<T){
        scanf("%d%d",&a,&b);
        printf("Case %d: %lld\n",t,get(a,b));
    }
    return 0;
}

N - Trailing Zeroes (III)

Ｎ：问阶乘有多少０,2的个数明显比５多得多，只要计算５的个数就行．

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
using namespace std;

int Find(int x){
    int sum = 0;
    while(x/5){
        sum+=x/5;
        x/=5;
    }
    return sum;
}


int main(){
    int t=0,T,a;
    scanf("%d",&T);
    while(t++<T){
        scanf("%d",&a);
        int b = a*4/5*5;
        while(Find(b)<a){
            b+=5;
        }
        if(Find(b) != a)printf("Case %d: impossible\n",t);
        else printf("Case %d: %d\n",t,b);
    }
    return 0;
}

O - GCD - Extreme (II)

O题是求解$\sum_{i < j \le N}gcd(i,j)$.考虑地推关系式：s(n) = s(n-1) +$\sum_{1 \le i < n} gcd(i,n)$

设$f(n) = \sum_{1 \le i <n}{gcd(i,n)}$;.按约数分类．gcd(x,n)=i的x有g(n,i)个;　

$f(n) = \sum i ·g(n,i)$ , gcd(x,n)=i也就是$gcd(\frac{x}{i}, \frac{n}{i}) = 1$ 也就是g(n,i) = $\phi(\frac{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
29
30
31
32
33
#include<cstdio>
#include<iostream>
#define ll long long
#define maxn 4000000
using namespace std;

ll phi[maxn+100]={0};
ll f[maxn+100],s[maxn+100];
void init_phi(){
    phi[1] = 1;
    for(int i = 2; i <= maxn; i++){
        if(!phi[i]){
            for(ll j = i; j <= maxn; j+=i){
                if(!phi[j])phi[j] = j;
                phi[j] = phi[j]/i*(i-1);
            }
        }
        for(ll j = 1; j*i<=maxn; j++){
            f[i*j]+=j*phi[i];
        }
    }
    for(int i = 1; i <= maxn; i++)
        s[i] += s[i-1] + f[i];
}

int main(){
    init_phi();
    int n;
    while(~scanf("%d",&n) && n){
        printf("%lld\n",s[n]);
    }
    return 0;
}

R - 青蛙的约会

R题是一道典型的扩展欧几里得的题目．

(m-n)x - ly = y-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
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
// ax+by = gcd(a,b); d = gcd(a, b)
void e_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a; x = 1; y = 0;
    }else{
        e_gcd(b, a%b, d, y, x);
        y -= (a/b)*x;
    }
}

int main(){
    ll x,y,m,n,l;
    while(~scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)){
        ll a,b,d,ans,x1,y1;
        e_gcd(m-n, -l, d, x1, y1);
        //printf("%lld:%lld:%lld\n",d,x1,y1);
        if((y-x)%d!=0){
            puts("Impossible");
        }else{
            x1 *= (y-x)/d;
            l /= -d;
            x1 %= l;
            if(x1 < 0)x1+=l;
            printf("%lld\n",x1);
        }
    }
}

S - C Looooops

S 题也是扩展欧几里得．

cx - $2^ky$ = b-a; 和上一道题是一样的．

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<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;

void e_gcd(ll a, ll b, ll &d, ll &x ,ll &y){
    if(!b){
        d = a;x = 1;y = 0;
    }else{
        e_gcd(b, a%b, d, y, x);
        y -= (a/b)*x;
    }
}

int main(){
    ll a,b,c,k;
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k) && k){
        ll d,x1,y1;
        e_gcd(c, (ll)pow(2,k), d, x1, y1);
        //printf("%lld:%lld:%lld",d,x1,y1);
        if((b-a)%d){
            puts("FOREVER");
        }else{
            x1 *= (b-a)/d;
            ll tmp = (ll)pow(2,k)/d;
            x1 %= tmp;
            if(x1<0)x1+=tmp;
            printf("%lld\n",x1);
        }
    }
    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
#include<cstdio>
using namespace std;
#define maxn 22222
bool judge[maxn]={0};

void init(){
    for(int i = 2; i < maxn; i++){
        if(!judge[i]){
            for(int j = i+i; j < maxn; j+=i)
                judge[j]=1;
        }
    }
    judge[1] = 1;
    judge[2] = 1;
}

int main(){
    init();
    int n;
    int t=1;
    while(~scanf("%d",&n) && n>0){
        printf("%d: %s\n",t++,judge[n]?"no":"yes");
    }
}

V - Maximum GCD

V题是暴力跑gcd,然而注意读入．这里使用了ungetc()函数，将读入的数字退回去．很神奇的函数，还没懂是怎么做到的．

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<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int a[111];
inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int main(){
    int t;scanf("%d",&t);
    while(getchar()!='\n');
    while(t--){
        int k=0;
        int maxn = 0;
        char c;
        while((c=getchar())!='\n'){
            if(c>='0' && c<= '9'){
                ungetc(c,stdin);
                scanf("%d",&a[k++]);
            }
        }
        for(int i = 0; i < k; i++){
            for(int j = i+1; j < k; j++){
                maxn = max(gcd(a[i],a[j]),maxn);
            }
        }
        printf("%d\n",maxn);
    }
    return 0;
}

W - Prime Time

求区间[a,b]内$n^2 + n + 41$是不是质数的概率．

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#define ll long long
using namespace std;

double a[11111];
ll f[11111]={0};

bool judge(ll n){
    for(int i = 2; i <= sqrt(n+0.5); i++){
        if(n%i==0)return false;
    }
    return true;
}

void init(){
    f[40]=1;
    for(int i = 41; i < 11110; i++){
        if(judge(1LL*i*i+i+41))f[i]=f[i-1];
        else f[i] = f[i-1]+1;
    }
}

int main(){
    init();
    int a,b;
    while(~scanf("%d%d",&a,&b)){
        ll ge;
        if(a<40){
            ge = b - f[b] - a + 1;
        }else{
            ge = b - f[b] - a + 1 + f[a-1];
        }
        double ans = ge*1.0/(b-a+1);
        printf("%.2lf\n",100*ans+1e-8);
    }
    return 0;
}

X - The equation

扩展欧几里得．这里先将系数变成正的，因为负数操作起来不等式方向容易改变．

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
#include<cstdio>
#include<cmath>
#include<iostream>
#define ll long long
using namespace std;

void e_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a;x = 1; y = 0;
    }else{
        e_gcd(b, a%b, d, y, x);
        y -= (a/b)*x;
    }
}

int main(){
    ll a,b,c,x1,y1,x2,y2;
    while(~scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x1,&x2,&y1,&y2)){
        ll d,x,y;
        c = -c;
        if(c<0){
            c=-c;a=-a;b=-b;
        }
        if(a<0){
            a=-a,swap(x1,x2),x1=-x1,x2=-x2;
        }
        if(b<0){
            b=-b;swap(y1,y2),y1=-y1,y2=-y2;
        }
        if(a==0||b==0){
            if(a==0&&b==0){
                if(c==0) printf("%lld\n",(x2-x1+1)*(y2-y1+1));
                else puts("0");
            }else if(a==0){
                if(c%b==0&&c/b>=y1&&c/b<=y2)printf("%lld\n",x2-x1+1);
                else puts("0");
            }else{
                if(c%a==0&&c/a>=x1&&c/a<=x2) printf("%lld\n",y2-y1+1);
                else puts("0");
            }
            return 0;
        }else{
            e_gcd(a,b,d,x,y);
            if(c%d) puts("0");
            else{
                ll temp = c/d;
                double addx = b/d,addy=a/d;
                x*=temp;
                y*=temp;
                ll r = min(floor((x2-x)/addx), floor((y-y1)/addy));
                ll l = max(ceil((x1-x)/addx),  ceil((y-y2)/addy));
                if(r>=l)printf("%lld\n",r-l+1);
                else puts("0");
            }
        }
    }
}

Y - Farey Sequence

也就是求有多少对(i,j)满足gcd(i,j)=1,而且i<j<=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
#include<cstdio>
#include<iostream>
using namespace std;
long long biao[1111111];
const int maxn = 1e6+10;
long long phi[maxn];
void init(){
    phi[1]=1;
    for(int i = 2; i <= maxn; i++){if(!phi[i])
        for(int j = i; j <= maxn; j+=i){
            if(!phi[j])phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
    for(int i = 1; i <= maxn; i++){
        biao[i] = biao[i-1]+phi[i];
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n) && n){
        printf("%lld\n",biao[n]-1);
    }
    return 0;
}

Z - The Super Powers

也就是按顺序打出$x^I$其中i不是质数．用set，自带排序功能．

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
unsigned long long maxn = ~0LL >> 1;
int biao1[] = {2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61};
int biao2[66];
set<unsigned long long> a;
int main(){
    for(int i = 0;biao1[i]; i++)biao2[biao1[i]]=1;
    for(unsigned long long i = 2;; i++){

        unsigned long long cnt= - 1,x = maxn;
        while(x){
            x/=i;
            cnt++;
        }
        if(cnt<4)break;
        unsigned long long temp = i*i;
        for(int j = 2;j <= cnt; j++ ){
            if(!biao2[j])a.insert(temp);
            temp*= i ;
        }
    }
    a.insert(1);
    for(set<unsigned long long>::iterator it = a.begin()++; it != a.end(); ++it){
        cout << *it << endl;
    }
    return 0;
}

还有ＢＰＱＴ四道题暂时未过，将放在侯一章开头．

本文标题:数论专题整理(1)

文章作者:呼哧

发布时间:2017-07-16, 18:40:42

最后更新:2018-08-04, 02:48:21

原始链接:http://hu-chi.github.io/2017/07/16/acm/数论基础专题整理(1)/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数论专题整理
    1. 1.1. A - Bi-shoe and Phi-shoe
    2. 1.2. C - Aladdin and the Flying Carpet
    3. 1.3. D - Sigma Function
    4. 1.4. E - Leading and Trailing
    5. 1.5. F - Goldbach`s Conjecture
    6. 1.6. G - Harmonic Number (II)
    7. 1.7. H - Pairs Forming LCM
    8. 1.8. I - Harmonic Number
    9. 1.9. J - Mysterious Bacteria
    10. 1.10. K - Large Division
    11. 1.11. L - Fantasy of a Summation
    12. 1.12. M - Help Hanzo
    13. 1.13. N - Trailing Zeroes (III)
    14. 1.14. O - GCD - Extreme (II)
    15. 1.15. R - 青蛙的约会
    16. 1.16. S - C Looooops
    17. 1.17. U - Primes
    18. 1.18. V - Maximum GCD
    19. 1.19. W - Prime Time
    20. 1.20. X - The equation
    21. 1.21. Y - Farey Sequence
    22. 1.22. Z - The Super Powers
|