首页 > 代码库 > CGCDSSQ
CGCDSSQ
这道题很妙啊。其实我们可以发现重要的不是起点和终点,重要的是个数,然后脑洞一下,可以递推。(我什么都没有想出来)假设我们已经知道了前面所有子串的gcd,那么我们可以用现在的a[i]和前面每个数求gcd,这样就把加入这个新元素的串的所有情况都枚举了一遍,因为gcd的数量很少,所以很快。枚举是存在一个新的map里,枚举完了以后,和老的map交换,因为我们只用上一次所有串,也就是必须用上一个字符,所以只用存上一次的情况就好了,然后把这次每个gcd的数量加进答案。(这里也许可以不用一个单独的map,挖)
#include<iostream> #include<vector> #include<map> #include<cstdio> #define Mp make_pair using namespace std; typedef pair<int,int> pii; map<int,int>mp; map<int,int>nextmp; map<int,long long>ans; int a[100010]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { int n,q; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { nextmp.clear(); for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++) { int temp1=a[i],temp2=it->first; if(temp1<temp2) swap(temp1,temp2); nextmp[gcd(temp1,temp2)]+=it->second; } nextmp[a[i]]++; swap(mp,nextmp); for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++) { ans[it->first]+=it->second; } } scanf("%d",&q); for(int i=1;i<=q;i++) { int x; scanf("%d",&x); printf("%I64d\n",ans[x]); } return 0; }
CGCDSSQ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。