Dylan's Blog
0%

Posted on Edited on In

问题描述：

我们要找出一个最小的 $L$ 的只由$8$构成的数，使它是$L$的整数倍。

输入：

由多组数据，每组数据一个数 $L$，输入以$0$结束 $L$($1≤L≤2000000000$)

输出：

一个数，表示数字的长度。如果不存在则输出$0$

思路：

一道比较玄学的题。这种只由一种数字构成相关问题都是一个套路吧。

先是将$8888…8$看成$(10^k-1)/9*8$。于是 $9L|8(10^k-1)$，等价为$10^k \equiv 1 (mod \frac{9L}{gcd(8, L)})$，这是一步特别重要的转化。

然后有这样的一个模型：若正整数$a, n$互质，那么满足$a^k \equiv 1 (mod n)$ 的最小正整数$k_0$一定是$ \varphi (n)$ 的约数。

因此，$k$一定为 $\varphi ( \frac{9L}{gcd(8, L)} ) $的约数。然后我们就可以枚举约数，再使用快速幂验证就OK了。有一个细节就是 $\varphi (n)$会大于MAX_INT所以要注意要再用快速乘防止爆$long long$。

代码：

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
69
70
#include 
#include 
#include 
#include 
#define LL long long
using namespace std;

LL l, Case, fac[20000005];

LL gcd(LL x, LL y)
{
    return y==0 ? x : gcd(y, x%y);
}

LL phi(LL n)
{
    LL ans=n;
    for(LL i=2; i*i<=n; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

LL ksc(LL x, LL y, LL p)
{
    LL ans=0;
    x%=p; y%=p;
    while(y)
    {
        if(y&1) ans=(ans+x)%p;
        x=(x+x)%p; y>>=1;
    }
    return ans;
}

LL ksm(LL x, LL y, LL p)
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=ksc(ans, x, p);
        x=ksc(x, x, p); y>>=1;
    }
    return ans;
}

int main()
{
    while(scanf("%lld", &l) && l)
    {
        int flag=0, cnt=0;;
        LL t1=l*9/gcd(l, 8);
        LL t2=phi(t1);
        for(LL i=1; i*i<=t2; i++)
            if(t2%i==0) fac[++cnt]=i, fac[++cnt]=t2/i;
        sort(fac+1, fac+cnt+1);
        for(LL i=1; i<=cnt; i++)
            if(ksm(10, fac[i], t1)==1)
            {
                printf("Case %lld: %lld\n", ++Case, fac[i]);
                flag=1;
                break;
            }
        if(!flag) printf("Case %lld: 0\n", ++Case);
    }
}

Posted on Edited on In

问题描述：

给出正整数$n$和$k$，计算$G(n, k) =k \% 1 + k \% 2 + … + k \% n$的值。

输入：

输入仅一行，包含两个整数$n$, $k$ ($1<=n, k<=10^9$)

输出：

输出仅一行，即$j(n, k)$。

思路：

直接计算原式肯定是会T的。。。我们可以根据 $a \% b=a-\lfloor a/b \rfloor *b$ 将原式变形。所以答案可以在$n*k$的基础上减去上式的后一部分得到。然后我们可以发现 $\lfloor a/b \rfloor$ 的取值是一段一段的，所以可以对于每一段用等差数列求和的公式得出答案。

复杂度似乎是$O( \sqrt{n} )$的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include 
#define LL long long
using namespace std;

LL n, k, ans;

int main()
{
    scanf("%lld%lld", &n, &k);
    ans=n*k;
    if(n>k) n=k;
    for(LL l=1, r; l<=n; l=r+1)
    {
        LL temp=k/l; r=min(k/temp, n);
        ans-=temp*(l+r)*(r-l+1)/2;
    }
    printf("%lld\n", ans);
}

Posted on Edited on In

问题描述:

　对于任何正整数$x$，其约数的个数记作$g(x)$。如果某个正整数$x$满足：$g(x)>g(i)$ 其中$0<i<x$，则称x为反质数。现在给定一个数$N$你需要找出不大于$N$的最大反素数。

输入：

一个数$N$（$1<=N<=2000000000$）。

输出：

不超过N的最大的反质数。

思路：

其实我们要求的就是$1-N$内约数个数最多的数（如果个数一样就是小的那个），然后我们可以利用一些神奇的性质用搜索解出答案。

首先反素数的质因子是不会超过10个的，并且质因子的指数是单调递减的。利用这两个性质缩小搜索范围，然后直接dfs枚举它的质因子就好了。

代码：

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
#include 
#define LL long long
using namespace std;

const int prime[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

LL n, maxsum, ans;

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum*=x;
        y>>=1; x*=x;
    }
    return sum;
}

void dfs(int id, int cnt, int sum, LL num)
{
    if(id==11)
    {
        if(sum>maxsum) ans=num, maxsum=sum;
        if(sum==maxsum) if(numn) break;
        dfs(id+1, i, sum*(i+1), num*ksm(prime[id], i));
    }
}

int main()
{
    scanf("%lld", &n);
    dfs(0, 30, 1, 1);
    printf("%lld\n", ans);
}

Posted on Edited on In

问题描述：

我们定义素数的距离为两个相邻素数之间存在合数的个数。给你一个区间$[l, r]$你需要求出区间内距离最大和最小的两对素数

输入：

有多组数据，每组数据两个数l, r 其中l, r不超过2147483647，区间大小不超过1000000

输出：

如果不存在两个质数输出”There are no adjacent primes.” 否则输出 “x1,x2 are closest, y1,y2 are most distant.”其中x1,x2,y1,y2为两对距离最大和最小的素数

思路：

由于l, r都很大，所以不方便之间线性筛。但区间大小不超过1000000，所以我们要利用好这个条件。

由于区间较小，我们可以利用类似于筛的方法筛掉区间的合数。我们可以先预处理出$2^{16}$内的素数，对于每一个区间我们通过枚举素数$prime[i]$，把区间内为$prime[i]$的倍数标记。枚举了所有素数后，区间内没有标记的数就是素数了。然后$O(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
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define MAXN 2000005
#define LL long long
using namespace std;

int l, r, tot, v[MAXN], prime[MAXN];
bool vis[1000005];

void getprime(int n)
{
    for(int i=2; i<=n; i++)
    {
        if(!v[i]) prime[++tot]=i, v[i]=i;
        for(int j=1; j<=tot; j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
}

int main()
{
    getprime(MAXN-5);
    while(scanf("%d%d", &l, &r)!=EOF)
    {
        if(l==1) l++;
        int ans1, ans2, ans3, ans4, last=-1, maxn=-1, minn=1e9;
        memset(vis, 0, sizeof(vis));
        for(int j=1; j<=tot; j++)
        {
            int x=((LL)l+prime[j]-1)/prime[j], y=r/prime[j];
            for(int i=max(2, x); i<=y; i++) vis[prime[j]*i-l]=1;
        }

        for(int i=0; i<=r-l; i++)
        {
            if(vis[i]) continue;
            if(last==-1) {last=i; continue;}
            if(i-last>maxn)
            {
                maxn=i-last;
                ans1=last+l; ans2=i+l;
            }
            if(i-last<minn)
            {
                minn=i-last;
                ans3=last+l; ans4=i+l;
            }
            last=i;
        }
        if(maxn==-1) printf("There are no adjacent primes.\n");
        else printf("%d,%d are closest, %d,%d are most distant.\n", ans3, ans4, ans1, ans2);
    }
}

Posted on Edited on In

问题描述：

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。

小G最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小）。

输入：

输入文件中的第一行为一个整数T，表示诗的数量。

接下来为T首诗，这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数N，L，P，其中：N表示这首诗句子的数目，L表示这首诗的行标准长度，P的含义见问题描述。

从第二行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成。

输出：

于每组测试数据，若最小的不协调度不超过10^18，则第一行为一个数，表示不协调度。接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。

如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过10^18，则输出“Too hard to arrange”（不含引号）。每组测试数据结束后输出“——————————”、。

思路：

这是一个DP应该不难想到，DP的方程也很简单：

然后我们需要将它优化，斜率优化能过6，7两个点，但后面的就比较难了。我们可以利用四边形不等式证明出这个DP是有决策单调性的(证明与p次方有关，利用什么求导搞。。反正我不懂)。然后就可以利用决策单调性来优化DP啦。

决策单调性是指：设$p[i]$为$f[i]$的最优决策，那么对于所有$j>i$都有$p[j]>=p[i]$。我们利用这个性质，可以利用单调队列+二分，在$O(nlogn)$内完成DP。

单调队列中的元素包含3个值：$p, l, r$，表示在区间$[l, r]$中的最优决策都是$p$。首先是把$(0, 0, n)$入队，然后对于每一个i： 1. 先检查队头元素的$[l, r]$是否包含了i，如果不包含就直接出队 2. 利用队头元素的最优决策$p$来更新$f[i]$ 3. 如果决策i比队尾的决策更优，那么我们就要插入决策i。于是我们就要找出区间$[l, r]$其中的最优决策都是i，首先$r$是为n（因为要靠后面决策来更新），$l$要利用二分找到。首先要清理队尾元素，也就是队尾元素整个区间$[l, r]$的决策i都更优，那么这个就可以出队。否则就在队尾元素区间$[l, r]$内二分，找到$l$的位置将决策i入队，并且更新队尾的$r$。

然后决策单调性的优化就是这样啦，自己理解了蛮久的。。。

代码

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
69
70
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long double
#define INF 1e18
#define MAXN 100005 
using namespace std;

int T, n, l, p, head, tail;
LL sum[MAXN], f[MAXN];
char str[MAXN];

struct Node {int p, l, r;} q[MAXN];

LL cal(int j, int i)
{
    LL num=1, x=sum[i]-sum[j]+i-j-1-l;
    for(int i=1; i<=p; i++) num*=abs(x);
    return f[j]+num;
}

int find(int l, int r, int j, int i)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(cal(j, mid)<cal(i, mid)) l=mid+1;
        else r=mid-1;   
    }
    return l;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &l, &p);
        for(int i=1; i<=n; i++)
        {
            scanf("%s", str);
            int len=strlen(str);
            sum[i]=sum[i-1]+len;
        }

        head=1, tail=0;
        q[++tail]=(Node){0, 0, n};
        for(int i=1; i<=n; i++)
        {
            if(head<=tail && i>q[head].r) head++;
            f[i]=cal(q[head].p, i);
            if(head>tail || cal(i, n)<=cal(q[tail].p, n))
            {
                while(head<=tail && cal(i, q[tail].l)<=cal(q[tail].p, q[tail].l)) tail--;
                if(head>tail) q[++tail]=(Node){i, i, n};
                else
                {
                    int pos=find(q[tail].l, q[tail].r, q[tail].p, i);
                    q[tail].r=pos-1;
                    q[++tail]=(Node){i, pos, n};
                }
            }
        }

        if(f[n]>INF) printf("Too hard to arrange\n");
        else printf("%lld\n", (long long)f[n]);
        printf("--------------------\n");
    }
}