题目

https://projecteuler.net/problem=129

题意

给一个整数n,(gcd(n,10)=1)，找最小的 111...111使得是n的倍数，A(n)返回这个最小的长度

A(7)=6,A(41)=5

求最小的n能让A(n) > 1000000的

存在性证明

题目说始终存在

因为$\text{gcd}(n,10) = 1$所以n不包含2和5这两个质因子

考虑结尾的字符为1,3,7,9

因为要证明的是任意n都能找到111...111，对于3,7,9结尾的，对应乘上7,3,9都会变成1 结尾的

那我们其实只要证明了 任何以1结尾的数，能找到111...111是它的倍数即可，我卡住了

对于给定n要找到,考虑它的每个质数因子p

$(10^i-1)/9 = 0 \pmod p$

费马小定理

$a^{p-1} - 1 = 0 \pmod p$

如果$p=3$, 有111是它的倍数(不是按照上面的公式, 因为有除以9的部分)

如果$p$是非2,3,5的质数

$10^{p-1}-1=0 \pmod p$

$(10^{p-1}-1)/9=0 \pmod p$

我们只得到

$10^{(p_1-1)(p_2-1)(p_3-1)} = 1 \pmod {p_1 p_2 p_3}$

但是如果有幂次质因子还是未知

和费马小定理相似但是更强劲的 欧拉定理

$a^{\varphi (n)} \equiv 1 \pmod{n}$

要求正好是 a和n互质

对于不含质因子3的$n$，能直接通过上式得到

$10^{\varphi (n)} \equiv 1 \pmod{n}$

$(10^{\varphi (n)} - 1)/9 \equiv 0 \pmod{n}$

对于含有3质因子的$n$,直接考虑9n

$10^{\varphi (9n)} \equiv 1 \pmod{9n}$

$10^{\varphi (9n)} - 1 \equiv 0 \pmod{9n}$

$(10^{\varphi (9n)} - 1)/9 \equiv 0 \pmod{n}$

得证

证明 $A(n) \le n$

考虑找到的$111\cdots 111$ 对应的商 $x = 111\cdots111 / n$

因为我们上面证明了$n$能整除，所以倒过来思考乘积如何填数

$x \cdot n = 111\cdots111$

因为 n 的末位是$1,3,7,9$中的奇数，那么 对于给定的尾数能直接确定商的尾数

同样我们能唯一确定十位,考虑每次计算后的余数

这里的余数是指 $((最少的前补1(\ge 0个) + 上一次的剩余值 - 当前商位上的数码\cdot n)/10) \pmod n$,

显然，上一次的剩余值通过个位数唯一决定 当前商的数码，又 前补1要最少又能满足表达式大于0,也是唯一方案。

因此 低$i$位的余数唯一确定$i+1$位的余数 $r_{i+1} = f(r_i)$，注意多个剩余值可能对应同一个余数，但这些余数相同的剩余值推导出的 高位的剩余值唯一

因此 考虑余数的变化，因为最终余数为零，所以中途余数不能成环。综上，商的位数不会超过$n$

因此原始的$111\cdots 111 = x\cdot n$ 也不会超过$n$

以7 举例, 说明上面的证明过程

$3\cdot 7=21,(111-21)/10 = 9 = 2 \pmod 7$

余数是控制链的长度，但是不影响计算 所以下面是109而不是102, 稍加理解的话是$102 - 6\cdot 7 = 109 - 7\cdot 7$

$7\cdot 7=49,(109-49)/10 = 6 = 6 \pmod 7$

$8\cdot 7=56,(106-56)/10 = 5 = 5 \pmod 7$

$5\cdot 7=35,(105-35)/10 = 7 = 0 \pmod 7$ // 同上不影响计算

$1\cdot 7 = 7, 7 - 7 = 0$

因此$15873 \cdot 7 = 111111$

余数变化是$2 \to 6 \to 5 \to 0$

对应上面唯一描述是

剩余值$11$,确定商的数码$3$,$3\cdot 7=21$,最少补充1个1,$(111-21=90)/10 = 9$,剩余值9,余数2

剩余值$ 9$,确定商的数码$7$,$7\cdot 7=49$,最少补充1个1,$(109-49=60)/10 = 6$,剩余值6,余数6

剩余值$ 6$,确定商的数码$8$,$8\cdot 7=56$,最少补充1个1,$(106-56=50)/10 = 5$,剩余值5,余数5

剩余值$ 5$,确定商的数码$5$,$5\cdot 7=35$,最少补充1个1,$(105-35=70)/10 = 7$,剩余值7,余数0

剩余值$ 7$,确定商的数码$1$,$1\cdot 7=7 $,最少补充0个1,7-7=0 结束

其实上面欧拉定理，我们只用关心 n 包含质因子3的情况，A(i) 是否会超过n

代码

幂次总是在小于 n的时候能模为1,这样可以从1000000开始

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

def A(v):
    p = 1
    for j in range(1, 9*v+1):
        p *= 10
        p %= 9*v
        if p % (9*v) == 1:
            return j


def main():
    maxAi = 0
    for i in range(500000-10, 1000000):
        ii = i*2+1
        if ii % 10 != 5:
            Ai = A(ii)
            # if Ai > ii:
            #     print(ii, Ai)
            if Ai - maxAi > 10000:
                maxAi = Ai
                print(ii, Ai)
            if Ai > 1000000:
                print(ii, Ai)
                break
    print("end")


main()

参考

https://mathlesstraveled.com/2011/11/16/fun-with-repunit-divisors-proofs/

https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem#Introductory

https://en.wikipedia.org/wiki/Euler%27s_theorem

题目

https://ac.nowcoder.com/acm/contest/8996/A

大意

n 由8个整数成分组成

1. 不超过1
2. 不超过2
3. 不超过3
4. 偶数个
5. 奇数个
6. 4的倍数
7. 不超过1
8. 3的倍数

题解

1. 打打表找规律直接得到公式

2. 生成函数

$(1+x)(1+x+x^2)(1+x+x^2+x^3)(\frac{1}{1-x^2})(\frac{x}{1-x^2})(\frac{1}{1-x^4})(1+x)(\frac{1}{1-x^3}) = \frac{x}{(1-x)^4}$

$=x(1+x+x^2+x^3…)^4$

只需要$x^N$的系数即可

题目

https://ac.nowcoder.com/acm/contest/9033/D

大意

给数组，和整数k

每次询问一个区间，它的所有子区间出现次数最多的数正好等于k的区间数

数组长度和询问数都是3e5

题解

我们要统计的是正好，

那么如果可以计算出 <=k,那么我们可以计算出<=k-1 然后想减少，只需要2倍时间

对于询问我们采取离线计算

下面问题变成如何计算 区间[l,r] 上满足 <=k 的方案数

考虑以 i 为起点，其对应的右侧<=k的分界点split(i2)。

很容易发现，这个分界点是随着i增加，单调递增的，因为如果 i1 < i2,那么[i2,split(i2)] 是最长的<=k，也就是其最多出现次数为k,那么[i1,split(i2)] 的最多出现次数,大于等于k,且[i1,split(i2)+1] 大于等于k+1

因此split(i1)<=split(i2)

有这个单调性质，我们很容易能扫一遍在O(n)时间内求出，每个左侧i的点，对应的右侧分界点

再一个O(n) 可以在不考虑选点范围的情况下，计算出 点对的前缀和presum[i] =presum[i-1]+(split(i)-i+1)

来看看和目标之间的差距

要求[l,r] 中间满足<=k 的点对数量

presum[r] - presum[l-1] 计算了左侧起点在[l,r]的满足<=k点对数量，但是没有对点对的右侧点进行限制

也就是需要去掉 左侧断点 [l,r] 内，但是右侧端点 >r的点对

= sum[i = l->r][ split(i) > r? split(i) - r: 0 ]

询问很多，不可能每次去计算，想前缀和之类，却 r和i没有直接关系，因为i是原始数组下标，而r是询问中提供的

拆分一下, 这样 前面部分可以通过 前缀和的方式统计，而后面的部分，只需要统计左端点在[l,r],右端点超过r的个数，在处理具体询问的时候乘上r即可。

= sum[i = l->r][ split(i) > r? split(i): 0 ] - sum[i = l->r][ split(i) > r? r : 0 ]

由此r从大到小处理询问即可。 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define MAXN 300010
ll n,q,k;
ll a[MAXN];

// 树状数组
void add(vector<ll>&arr,ll x,ll y) {
  for(; x <= n; x += lowbit(x)){
    arr[x] += y;
  }
}
ll sum(vector<ll>&arr,ll x) {
  ll ans = 0;
  for(; x > 0; x -= lowbit(x)){
    ans += arr[x];
  }
  return ans;
}
ll sto(vector<ll>&arr,ll l,ll r) {
  return sum(arr,r) - sum(arr,l-1);
}

// [值] = 下标数组
vector<ll>v[MAXN];
// 离线 询问
struct ask {
  ll l,r,i;
}w[MAXN];

ll ans[MAXN];

bool cmp(ask a,ask b) {
  return a.r > b.r;
}

// < k
void solve(ll k,ll pw) {
  priority_queue< pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>> >p; // {idx,value}
  rep(i,1,n+1){
    if(v[i].size() >= k){
      // 首个超过 k个的坐标和值
      p.push({v[i][k-1],i});
    }
  }
  vector<ll> cnt(MAXN,0);
  vector<ll>l2r(MAXN,0); // 以i为区间左端点，右侧端点选取(>=k)范围的左侧
  vector< vector<ll> > r2l(MAXN,vector<ll>());
  rep(i,1,n+1){
    while(!p.empty() && (
          // 之后的部分个数 小于k
          cnt[p.top().second] + k-1 >= v[p.top().second].size() ||
          // 每次用完了头部不pop，靠这个来避免重复？
          v[p.top().second][cnt[p.top().second] + k-1] != p.top().first
          )){
      p.pop();
    }
    // 扫描到当前 a[i] 出现的次数
    cnt[a[i]] ++;
    // 后续可出现连续 k个a[i]
    if(v[a[i]].size() > cnt[a[i]]+k-1){
      p.push({v[a[i]][cnt[a[i]]+k-1],a[i]});
    }
    l2r[i] = p.empty()?n:(p.top().first - 1);
    // 右侧区间的左侧坐标 -> 左端点, 从i到f[i] 这一段 最大次数小于k
    r2l[l2r[i]].pb(i);
  }

  // [0->i]为左端点不合法个数前缀和
  vector<ll>s(MAXN,0);
  rep(i,1,n+1){
    // 表示<k的对的方案数
    s[i] = s[i-1] + l2r[i]-i+1;
  }
  // 树状数组
  vector<vector<ll> >tr(2, vector<ll>(MAXN,0));
  ll nn = 0;
  // 询问从右向左处理
  per(i,1,n+1){
    while(w[nn].r >= i && nn < q) {
      ans[w[nn].i] += pw*(
          // 小于k 的对数方案
          (s[w[nn].r] - s[w[nn].l-1])
          // 当前  大于k 的对数方案
          +sto(tr[0],w[nn].l,w[nn].r)+w[nn].r*sto(tr[1],w[nn].l,w[nn].r)
      );
      nn ++;
    }
    rep(j,0,r2l[i].size()){
      ll xay = r2l[i][j];
      // 大于等于k的对数
      add(tr[0],xay,-i);
      // 次数
      add(tr[1],xay,1);
    }
  }
}

int main() {
  scanf("%lld %lld %lld",&n,&q,&k);
  rep(i,1,n+1){
    cin >> a[i];
    v[a[i]].pb(i);
  }
  rep(i,0,q){
    scanf("%lld %lld",&w[i].l,&w[i].r);
    w[i].i = i;
  }
  // 询问 右侧r 从大到小排列
  sort(w,w+q,cmp);

  solve(k+1,1);
  if(k != 1){
    solve(k,-1);
  }
  rep(i,0,q){
    printf("%lld\n",ans[i]);
  }
  return 0;
}

收获总结

1. =k如果难算，可以变成计算<=k 和 <=k-1 然后进行 相减
2. 离线处理询问
3. 处理“不能”前缀和的部分，拆分成可前缀和的部分，和部分统计，询问时再乘积的部分分别处理，降低到O(n)
4. 在有前缀和的代码里 用1-index比0-index方便一些

题目

https://projecteuler.net/problem=106

题目说，S(集合)表示集合元素的和

集合A如果它任何不相交的两个子集B和C，同时满足

1. S(B) != S(C)
2. 如果 B的元素个数比 C多，那么 S(B)>S(C)

那么A是满足题意的

问 现在 给了一个集合，元素个数是n且满足第二条，要测试多少对 子集， 才能判定它是满足题意的

然后举例

n=4 是25中的 1对

n=7 是 966中的70对

求 n=12 时 需要判断的是261625中的多少对

理解

我是没想到，还能在ProjectEuler练习语文

注意到 一对不相交子集 如果元素个数不同，那么满足2一定不满足1,所以，如果“可能”满足1,那么元素个数相等

那么首先说 n=4时25怎么来的

假设四个元素 且排序了的 {A,B,C,D}

一个元素的比对就是 3+2+1=6,

两个元素的比对 3 种

因为不相交 所以 3个以上元素的不比对

所以哪里来的 25呢？？？？？？？？？？？？

换个思路

假设比对是有序的也就是 x和y比，y和x比 算两种，那么方案数一定是2的倍数？也不会25？

再说先放弃不相交的性质，只要不相等就计数？

1
2
3

1个元素 3+2+1=6
2个元素 5+4+3+2+1 = 15
3个元素 3+2+1=6

就是出不来25啊

一个办法是结束吧，放弃吧，只去关心1是怎么来的

然后我甚至想到了勾股定理4x4+3x3=25 然而也不是

难道是没考虑2的时候，之考虑了不相交

1
2
3
4

1对比1 3+2+1=6
1对比2 4x3 = 12
1对比3 4x1 = 4
2对比2 3

还真的是25

按照这个思路，尝试一下n=7,是不是966

1
2
3
4
5
6
7
8
9
10
11
12
13
14

1v1:6+5+4+3+2+1 = 21
1v2:7x15=105
1v3:7x20=140
1v4:7x15=105
1v5:7x6=42
1v6:7x1=7
2v2:6x(5x4/2)+5x(4x3/2)+4x(3x2/2)+3x(2x1/2) = 105
2v3:21x10=210
2v4:21x5=105
2v5:21x1=21
3v3:15x4+10*1=70
3v4:35x1=35

21+105+140+105+42+7+105+210+105+21+70+35=966

那么这样说真的就是这个值了，不过n=12时这个值并不需要我们求

解

然后我们来看看 什么是可能

n=4, {A,B,C,D}

个数不相等的两个子集 一定不等

1v1 一定不等

2v2有 AB vs CD , AC vs BD, AD vs BC, 而只有AD vs BC是“可能”的，前面两组根据大小偏序关系一定不等

没有3v3以及以上

那么对于任意n呢

先看看n=7，{ABCDEFG}

1v1老样子一定不等

还剩下2v2和3v3

对于 2v2，一定是 一个的最小到最大构成的区间，包含另一个，

1
2
3
4
5
6
7
8
9
10
11
12

BC为中间:1x4=4
BD为中间:1x3=3
BE为中间:1x2=2
BF为中间:1x1=1
CD为中间:2x3=6
CE为中间:2x2=4
CF为中间:2x1=2
DE为中间:3x2=6
DF为中间:3x1=3
EF为中间:4x1=4

4+3+2+1+6+4+2+6+3+4=35

对于3v3,

X1<Y1<X2<Y2<X3<Y3一定不行， 7个

X1<X2<X3<Y1<Y2<Y3一定不行， 7个

X1<X2<Y1<X3<Y2<Y3一定不行， 7个

X1<X2<Y1<Y2<X3<Y3一定不行， 7个

X1<Y1<X2<X3<Y2<Y3一定不行， 7个

所以可行的3v3是 70-5x7=35 个

总共 35+35是70个

那么根据上面看到 实际上，不可能就是

两个子集排序后，对应下标位置偏序一致

代码

还需要代码吗，这题核心是语文的阅读理解，猜作者的意图

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

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)

int ia = 0;
int a[20];
int ib = 0;
int b[20];

int possible = 0;

int N = 12;

bool test_possible(){
  if(ia != ib)return false;
  int gcnt=0;
  int lcnt=0;
  rep(i,0,ia){
    if(a[i]< b[i]){
      lcnt++;
    }else{
      gcnt++;
    }
  }
  return lcnt != 0 && gcnt != 0;
}

void tryidx(int index){
  if(index == N){
    possible += test_possible();
    return;
  }
  a[ia++] = index;
  tryidx(index+1);
  ia--;
  if(ia != 0){
    b[ib++] = index;
    tryidx(index+1);
    ib--;
  }

  tryidx(index+1);
}


int main(){
  cin>>N;
  tryidx(0);
  printf("%d\n",possible);
  return 0;
}

题目

https://projecteuler.net/problem=122

Addition chain

理解

看起来是个描述很简洁的题目

但是 我以为能有什么 局部最优

所以想说 15=3x5,也就是做一次 变3的工作 再一次变5的工作

对于质数 = 1+它的分解

然而错了

想不出什么方法，翻了翻wiki找到了上面的Addition chain

说计算addition chains目前是一个 NP-complete 的问题

好像也并不能dp

于是考虑生成过程，写了一个树上爆搜。

也就是 每个节点的子节点 等于该节点和，该节点以及祖先节点的和

这样就是加法过程，每次新增的数都是最大的。 但是这种情况 其实没有考虑 A-B-C-D-(D+B)-(D+C) , 这样就不是最后一个增加？

这样算法，感觉是有bug的？

虽然这样的代码过了。

不过，我打出了 bfs的 元素个数，看得到仅仅200的数据。191， 已经下标达到了4053954。

然后 我对拍了一下数据，最小的一个不一致是23，需要6步，而我错误的dp是7步

7步: 1+1=2,2+2=4,4+1=5,5+5=10,10+1=11,11+11=22,22+1=23

6步: 1+1=2,2+2=4,4+1=5,5+4=9,9+9=18,18+5=23

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

namespace X{
  ll r(){ll r;scanf("%lld",&r);return r;} // read
  void add(ll &v0,ll &v1){(v0+=v1%MOD)%=MOD;} // add with MOD
  ll mpow(ll v,ll mi){ll r = 1;while(mi){if(mi%2)(r*=v)%=MOD;(v*=v)%=MOD;mi>>=1;};return r;} // quick power with MOD
  ll mod(ll v){return (v%MOD+MOD)%MOD;} // output
  ll gcd(ll a,ll b){return b == 0?a:gcd(b,a%b);}
};

// 错误的方法 start
ll dp[210];
int p[210];

void wayWrong(){
  p[1] = 1;
  rep(i,2,20){
    if(!p[i]){
      for(int j = i*i;j<=200;j+=i){
        if(!p[j]){
          p[j]= i;
        }
      }
    }
  }
  rep(i,2,201){
    if(!p[i]){
      dp[i] = 1+dp[i-1];
    }else{
      dp[i] = dp[p[i]] + dp[i/p[i]];
    }
  }
}

// 错误的方法 end

struct Node{
  int dep = 0 ;
  int val = 0;
  Node * fa = NULL;
};

const int N = 10000000;

Node nodes[N+10];

int leftcnt = 200 - 1 ;
ll ans[210];

int main(){
  int st = 0;
  int rear = 1;
  nodes[0].val = 1;
  while(st < rear){
    Node * p = &nodes[st];
    while(p != NULL){
      int newval = p->val + nodes[st].val;
      if(newval <= 200){
        if(ans[newval] == 0){
          printf("%d[dep:%d][bfs idx:%d]\n",newval,nodes[st].dep,rear);
          ans[newval] = nodes[st].dep + 1;
          leftcnt--;
          if(leftcnt == 0){
            break;
          }
        }
        nodes[rear].fa = &nodes[st];
        nodes[rear].dep = nodes[st].dep+1;
        nodes[rear].val = newval;
        rear++;
        if(rear > N){
          printf("leftcnt:%d\n",leftcnt);
          rep(i,1,201){
            if(!ans[i]){
              printf("noans:%lld\n",i);
            }
          }
          return 0;
        }
      }
      p=p->fa;
    }
    st++;
    if(leftcnt == 0){
      break;
    }
  }
  ll count = 0;
  rep(i,1,201){
    count += ans[i];
    // printf("%lld:%lld\n",i,ans[i]);
  }
  printf("%lld\n",count);
  return 0;
}