tea5.13-5.17

茶5.13-5.17

只能做出来周一-周三，周四看题解勉强会，周五不想看了

Mon

Points on Line

题目翻译：

小Petya非常喜欢积分。最近，他妈妈给了他 OX 线上的 n 个点。现在 Petya 想知道有多少种方法可以选择三个不同的点，使得其中最远的两个点之间的距离不超过 d。

请注意，三个所选点组内点的顺序并不重要

输入：

第一行 n和d (1<=n<=105;1<=d<=109).接下来一行包括n个整数，绝对值不超过109，代表Petya 得到的点的 x 坐标。

输出：

打印一个整数 — 三点组的数量，其中两个最远点之间的距离不超过 d。

Sol:

让我们选择三元组的最右边点。为此，我们可以按 X 坐标的升序遍历所有点。同时，我们将保持一个指向最左边点的指针，该指针位于与当前最右边点的距离不超过 d 的距离上。我们可以很容易地找出两个指针之间的线段中的点数，不包括最右边的点。我们称这个数字为 k。然后正好存在 k * （k - 1） / 2 个具有固定最右边点的三元组点。剩下的唯一事情就是将这些值相加以获得所有最右边的点。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
    int n,d;
    cin>>n>>d;
    vi a(n);
    for(int i = 0; i < n; i++) {
        cin>>a[i];
    }
    int j = 0;
    long long ans = 0;
    for (int i=0;i<n;i++) {
        while (a[i]-a[j] > d) j++;
        ans += (long long)(i-j)*(i-j-1)/2;
    }
    cout<<ans<<endl;
}

Tue

Vasya and Petya’s Game

题目翻译：

Vasya 和 Petya 正在玩一个简单的游戏。Vasya 想到了 1 和 n 之间的数字 x，Petya 试图猜测这个数字。

Petya 可以问这样的问题：“未知数可以被数 y 整除吗？

游戏按照以下规则进行：首先Petya问所有他感兴趣的问题（而且，他可以不问任何问题），然后Vasya用“是”或“否”回答每个问题。在收到所有答案后，佩蒂亚应该确定瓦夏想到的数字。

不幸的是，佩蒂亚并不熟悉数论。帮助他找到他应该问的最少问题数量，以保证猜测 Vasya 的数字，以及他应该问的问题。

输入：

一个整数n(1<=n<=103).

输出：

打印问题序列 k (0 ≤ k ≤ n) 的长度，后跟 k 个数字 — 问题 yi (1 ≤ yi ≤ n)。

思路：

如果Petya没有问pk，其中p是素数且k ≥ 1，他将无法区分pk - 1和pk。 也就是说，他应该问所有的数字pk。很容易证明这个序列实际上猜出了从 1 到 n 的所有数字

code:

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
void solve()
{
    int n;
    cin >> n;
    vi is_prime(n + 1, true), primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (is_prime[i]) {
            int q = 1;
            while (q <= n / i) {
                q *= i;
                ans.push_back(q);
            }
        }
    }
    cout<<ans.size()<<endl;
    for (auto e:ans) cout<<e<<" ";
    cout<<'\n';
}

Wed

Two Arrays and Sum of Functions

题目翻译：

给你两个数组a和b，长度都为n

定义一个函数：

f(l,r)=\sum_{l<=i<=r}a_i * b_i

您的任务是对数组的元素重新排序（选择任意元素顺序）𝑏 来最小化

\sum_{1<=l<=r<=n}f(l,r)

由于答案可能非常大，因此您必须以 998244353 为模来打印它 998244353 。请注意，您应该最小化答案，但不要最小化其余数。

输入：

第一行一个整数n（1<=n<=2*105),代表数组a和b的长度

第二行包含n个整数a1,a2,a3,…,an(1<=ai<=106)

第二行包含n个整数b1,b2,b3,…,bn(1<=bi<=106)

输出：

一个整数，代表上述函数的最小可能值

思路：

让我们使用对求和技术的贡献来解决这个问题。值 ai⋅bi 会在答案里出现多少次呢？它将发生 i⋅（n−i+1）次。好的，现在我们可以看到，对于每个位置 i 我们的值为 ai⋅bi⋅i⋅（n−i+1）.唯一的非常量值是 bi.所以设 vali=ai⋅i⋅（n−i+1）.请注意，您不能在此处取此值模998244353因为那样就无法正确比较这些值。我们应该配对最小 bi
具有最大 vali，第二个最小值与第二个最大值，依此类推。因此，让我们对数组 val 进行排序和数组 b，反转数组 b 并计算值 Vali⋅bi 的总和（不要忘记这里的模数！)

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    int n;
    cin>>n;
    vi a(n), b(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    for(int i = 0; i < n; i++) cin>>b[i];
    sort(b.begin(), b.end());
	vector<pair<long long, int>> val(n);
	for (int i = 0; i < n; ++i) {
		val[i].first = (i + 1) * 1ll * (n - i) * a[i];
		val[i].second = i;
	}
	sort(val.rbegin(), val.rend());
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = (ans + (val[i].first % MOD * 1ll * b[i]) % MOD) % MOD;
	}
	cout << ans << endl;
}

Thu

Vasilije Loves Number Theory

题目翻译：

Vasilije 是一个聪明的学生，他的离散数学老师 Sonja 把他的数论教得很好。他给了 Ognjen 一个正整数 𝑛 。

表示 𝑑(𝑛) 作为 𝑛 的正整数除数的数量，并表示 𝑔𝑐𝑑(𝑎,𝑏) 作为最大整数 𝑔 这样 𝑎 可以被𝑔整除和 𝑏 可以被𝑔整除。

之后，他给了 Ognjen 𝑞 个查询，有 2 种查询类型。

  • 1 𝑥 — 设置 𝑛 到 𝑛⋅𝑥 ，然后回答以下问题：是否存在正整数𝑎 使得 𝑔𝑐𝑑(𝑎,𝑛)=1 ，并且 𝑑(𝑛⋅𝑎)=𝑛 ？
  • 2 - 重置n为其初始值（在任何查询之前）

请注意 𝑛 在类型 1 查询后不会返回到其初始值。

由于 Ognjen 害怕数论，Vasilije 向他保证，每次查询后，𝑑(𝑛)≤109然而，即使有这样的限制，他仍然需要你的帮助来解决这个问题。

输入：

第一行包含一个正整数𝑡 , (1≤𝑡≤100) — 测试用例的数量。

每个测试用例的第一行包含2 整数，𝑛 和𝑞 (1≤𝑛≤106, 1≤𝑞≤1000) — 数字 𝑛 以及查询的数量。

以下𝑞 行包含一个整数 𝑘 (1 ≤ 𝑘 ≤ 2 ), 如果 𝑘=1 那么这一行还有另一个整数𝑥 (1 ≤ 𝑥 ≤ 106) — 查询的描述。

对于给定的输入，保证 𝑑(𝑛) 不超过109在任何时候。 保证 𝑞 的总和所有测试用例不超过103 。

输出：

对于每个类型 1 查询，如果满足条件输出“YES”，否则输出“NO”。

思路：

当且仅当d(n)整除于n是存在解

proof：

证明

code：

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vll vector<ll>
#define pb(x) push_back(x)
#define out(x) cout<<x<<endl;
#define pii pair<int,int>
#define mii map<int,int>
#define mp(x,y) make_pair(x,y)
#define MOD 1000000007
#define F first
#define S second
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); ++(i))
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); --(i))
#define BUG(x) cerr << #x << " = " << (x) << endl
#define sort(a) sort (a.begin(),a.end())
//#define rsort(v) sort(v.rbegin(),v.rend());
#define gsort(a) sort(a.begin(), a.end(), greater<ll>())
#define rvs(a) reverse(a.begin(),a.end())
#define ctv(v) for(auto it:v)cout<<it<<' '; cout<<endl;
#define cnv(v) for(auto &it:v) cin>>it;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define v_sum(a) accumulate(a.begin(),a.end(),0)
#define v_min(a) *min_element (a.begin(),a.end())
#define v_max(a) *max_element (a.begin(),a.end())
#define upbd(v,x) upper_bound(v.begin(),v.end(),r)
#define lwbd(v,x) lower_bound(v.begin(),v.end(),r)
#define sp cout<<fixed<<setprecision(10)<<num<<endl
#define test ll t;cin>>t;while(t--)
#define gap " "
const int N=2e6+10;
const ll mod=1000000007;
#define INF 1e18;
#define print(a) for(auto e:a) cout<<e<<' ';
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define xd ios_base::sync_with_stdio(false); cin.tie(NULL);
namespace io {
    void fastio()
    {
        ios::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);
    }
    inline int read()
    {
        char op = getchar(); int x = 0, f = 1;
        while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
        while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 0x30), op = getchar();
        return x * f;
    }
    inline void write(int x)
    {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + 0x30);
    }
} using namespace io;
mii powers;
mii original_divisors;
int smallest_divisor[N];
bool mark[N];
ll divisor_count = 1;
void prime(){ //calculates the smallers divisor for each number from 1 to N (sieve of erathosetenes)
	smallest_divisor[1]=1;
	smallest_divisor[2]=2;
	for(int i=4; i<N; i+=2){
		mark[i]=true;
		smallest_divisor[i]=2;
	}	
	for(int i=3; i<N; i+=2){
		if(!mark[i]){
			smallest_divisor[i]=i;
			for(ll j = i*1ll*i; j<N; j+=2*i){
				if(!mark[j]){
					smallest_divisor[j]=i;
					mark[j]=1;
				}
			}
		}
	}
}
void factorize(int x){ 
	int p=0;
	int current_divisor = 1;
	while(x>1){ //while x has non 1 divisors, divide it by it's smallest divisor which isn't 1(smallers divisor if always prime)
		if(smallest_divisor[x]!=current_divisor){
			if(p>0){
				divisor_count/=powers[current_divisor]+1;
				powers[current_divisor]+=p;
				divisor_count*=powers[current_divisor]+1;
			}
			p=1;
			current_divisor=smallest_divisor[x];
		}
		else{
			p++;
		}
		x/=smallest_divisor[x];
	}
	if(p>0){
		divisor_count/=powers[current_divisor]+1;
		powers[current_divisor]+=p;
		divisor_count*=powers[current_divisor]+1;
	}
	return;
}
void solve()
{
    int n; int q;
    cin >> n >> q;
    factorize(n);
    for(auto prime : powers){
        original_divisors[prime.first]=prime.second;
    }
    int original_divisor_count = divisor_count; 
    vector<int> queries;
    while(q--){
        int query_type;
        cin >> query_type;
        if(query_type==1){ 
            int x;
            cin >> x;
            factorize(x); 
            queries.push_back(x); 
            ll num=n;
            for(int query : queries){ 
                num*=query;
                num%=divisor_count;
            }
            if(num==0){ 
                cout << "YES\n";
            }
            else cout << "NO\n";
        }
        else{ 
            powers.clear(); 
            for(auto original_div : original_divisors){
                powers[original_div.first]=original_div.second;
            }
            divisor_count=original_divisor_count; 
            queries.clear(); 
        }
    }
    original_divisors.clear();
    powers.clear();
    divisor_count=1;
    original_divisor_count =1;
}
int main()
{
    xd
    prime();
    test{
        solve();
        if(t) cout << "\n";
    }
}
codeforces
#math #algorithm #tea
tea5.13-5.17
https://www.polarishaw.top/2024/05/17/tea5-13-5-17/
作者
Polaris
发布于
2024年5月17日
许可协议