BAPC2017 UPC Collatz Conjecture (数论GCD, 去重优化)

本文主要是介绍BAPC2017 UPC Collatz Conjecture (数论GCD, 去重优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4981: Collatz Conjecture

时间限制: 6 Sec 内存限制: 128 MB
提交: 210 解决: 21
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

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 equalled 1. 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.

输入

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 a single line containing a single integer, the number of distinct values f takes on over the given sequence.

样例输入


9 6 2 4

样例输出

提示

来源

BAPC2017

题意：对于n个数字的连续子串中，有多少个不同的gcd。

题解：枚举子串中最后一个元素，便可表示出所有子串的gcd，存到ans数组中，最后unique去重(必须有序)即可。

#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}const int MAXN=1e6+7;
ll a[MAXN],g[MAXN],ans[10*MAXN];
int main()
{ll n;scanf("%lld",&n);for(int i=0;i<n;i++)scanf("%lld",&a[i]);ll tot=0,cot=0;for(int i=0;i<n;i++){for(int j=0;j<tot;j++){ll x=gcd(a[i],g[j]);if(x!=g[j]){ans[cot++]=g[j];g[j]=x;}}g[tot++]=a[i];tot=unique(g,g+tot)-g;}for(int i=0;i<tot;i++)ans[cot++]=g[i];sort(ans,ans+cot);ll ret=unique(ans,ans+cot)-ans;printf("%lld\n",ret);return 0;
}

这篇关于BAPC2017 UPC Collatz Conjecture (数论GCD, 去重优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！