Gym 101666C Collatz Conjecture
Description
In 1978 AD the great Sir Isaac Newton, whilst proving that P is a strict superset of N P, defined the Beta Alpha Pi Zeta function f as follows over any sequence of positive integers a1, . . . , an. Given integers 1 ≤ i ≤ j ≤ n, we define f(i, j) as gcd(ai, ai+1, . . . , aj−1, aj ).
About a century later Lothar Collatz applied this function to
the sequence 1, 1, 1, . . . , 1, and observed that f always equalled1.Based on this, he conjectured that f is always a constant function, no matter what the sequence ai is. This conjecture, now widely known as the Collatz Conjecture, is one of the major open problems in botanical studies. (The Strong Collatz Conjecture claims that however many values f takes on, the real part is always 1/2)
You, a budding young cultural anthropologist, have decided to disprove this conjecture. Given a sequence ai, calculate how many different values f takes on.
Input
The input consists of two lines.
• A single integer 1 ≤ n ≤ 5 · 105
, the length of the sequence.
• The sequence a1, a2, . . . , an. It is given that 1 ≤ ai ≤ 1018
.
Output
Output a single line containing a single integer, the number of distinct values f takes on over
the given sequence.
Sample Input 1
4
9 6 2 4
Sample Output 1
6
Sample Input 2
4
9 6 3 4
Sample Output 2
5
题解
题意
给出序列，给定计算方法f(i,j)表示i到j区间的gcd的值。对于一个序列，求f(i,j)有多少种不同的值。
思路
最暴力的想法，就是对于每个值都向后扫，直到gcd为1时，跳出。由于1e18最多是2^64，所以最多扫64次就会跳出。然而快速读入之后还是T了，看来数据专门卡了这种情况。
所以可以采用两个unordered_set滚动保存还在的值，如果变为1，不进入set。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include <unordered_set>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int T;
namespace fastIO {
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pend == p1) {
IOerror = 1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '
' || ch == '
' || ch == ' ';
}
inline int rd(ll &x) {
char ch;
while(blank(ch = nc()));
if(IOerror) return -1;
for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
return 1;
}
#undef BUF_SIZE
};
using namespace fastIO;
inline ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
const int MAXN = 1e6+10;
ll a[MAXN];
unordered_set<ll> us1;
unordered_set<ll> us2;
unordered_set<ll> ans;
unordered_set<ll>::iterator iter;
int main() {
register int T = 0;
scanf("%d",&T);
for(register int i=0;i<T;i++) rd(a[i]);
us1.insert(a[0]);
ans.insert(a[0]);
for(register int i=1;i<T;i++){
us2.insert(a[i]);
for(iter=us1.begin();iter!=us1.end();iter++){
ll cur = gcd(*iter,a[i]);
us2.insert(cur);
}
us1.clear();
for(iter=us2.begin();iter!=us2.end();iter++){
if((*iter)!=1) us1.insert((*iter));
ans.insert((*iter));
}
us2.clear();
}
ll num = ans.size();
printf("%lld
",num);
return 0;
}