列表

详情

NC223710. SumandProduct

描述

Sarah and Patricia are young, very gifted sisters. Ever since they learned arithmetic in preschool, they have been bothering their mother Marguerite day and night to practice their calculations. Marguerite bought the two girls an arithmetic practice book, which has n pages and a positive integer on each page. Those integers can be used for practicing arithmetic calculations. Marguerite hopes that the book can keep the two girls busy for a while so that she can work on her other chores.
Sarah and Patricia need to know whether their calculated answers are right, but Marguerite does not have the time to check their work. She therefore comes up with the clever idea of adversarial toddler training. Marguerite knows that Sarah is good at addition and Patricia is talented in multiplication. So she first chooses a range of consecutive book pages (at least two), and then asks Sarah to calculate the sum of the integers on these pages, and asks Patricia to calculate the product of these integers. If she chooses the pages carefully, then the two girls’ answers would be the same, and she can simply let Sarah and Patricia compare their answers!
As Sarah and Patricia do not want to practice on the same range multiple times, Marguerite wants to know in how many different ways she can select a range of pages for her toddler training (and when to buy a new practice book).

输入描述

The input has a single integer n (2 ≤ n ≤ 2 · 105 ) on the first line. The second line has n positive integers giving thenumbers in the arithmetic practice book ordered by the pages. None of these integers are larger than 109 . 

输出描述

Output a single integer, the number of ways for Marguerite to choose a range of at least two consecutive pages so that Sarah’s answer matches Patricia’s.

示例1

输入: 

5
2 2 1 2 3

输出: 

2

示例2

输入: 

8
1 2 4 1 1 2 5 1

输出: 

4

示例3

输入: 

4
5 6 7 8

输出: 

0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 68ms, 内存消耗: 1952K, 提交时间: 2021-08-19 13:14:22 

#include <cmath>
#include <cstdio>
#include <algorithm>

const int maxn = 2E+5 + 5;

int n, a[maxn], lst[maxn];

int main() {
    scanf("%d", &n);
    for(int i = 1, LST = 0; i <= n; ++i) {
        scanf("%d", &a[i]), lst[i] = LST;
		if(a[i] != 1) LST = i;
    }

	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		int u = i;

		__int128 prod = 1, sum = 0;
		while(u) {
			prod *= a[u], sum += a[u];
			if(prod >= 1E+14) break;
			int cnt = u - lst[u] - 1;
			if(sum <= prod && sum + cnt >= prod) ++ans;
			sum += cnt, u = lst[u];
		}
	}
	printf("%d\n", ans - n);
}

上一题

© 2025 nowcoder.com