14573

수열의 관계식은

A(n) = A(n-1) * (2^(n-2) + 2) (단 n >= 3)

그러므로

최대 공약수는 A(1)*A(min(i,j))

최소 공배수는 A(1)*A(max(i,j))

공배수는 2의 거듭제곱을 구해야 하므로

A(1)의 거듭제곱 + max(i,j) - 1 (단 i,j>=3)

합은 부분합을 이용 A(1)*(sum(j)-sum(i))

k번째 A(1)*A(k)

아래는 소스코드이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

int q;

long long pre[1000001], sum[1000001];

int main () {

freopen("sample.txt", "r", stdin);

scanf("%d",&q);

long long c = 2;

sum[1]=pre[1]=pre[2]=1; sum[2]=2;

for(int i=3;i<1000001;i++){

pre[i] = (pre[i-1] * (c+2)) % MOD;

sum[i] = (sum[i-1] + pre[i]) % MOD;

c = (c*2) % MOD;

}

for(int k=0,type,a,i,j;k<q;k++){

scanf("%d",&type);

if(type == 1){

scanf("%d%d%d",&a,&i,&j);

int small = min(i,j);

printf("%lld\n",(a*pre[small])%MOD);

}

else if(type == 2){

scanf("%d%d%d",&a,&i,&j);

int ret = 0, big = max(i,j);

for(int x=2,y=1;x<=a;x*=2,y++) if(a%x == 0) ret = y;

if(big > 2) ret += big - 1;

printf("%d\n",ret);

}

else if(type == 3){

scanf("%d%d%d",&a,&i,&j);

printf("%lld\n",((MOD+sum[j]-sum[i-1])*a)%MOD);

}

else{

scanf("%d%d",&a,&i);

printf("%lld\n",(a*pre[i])%MOD);

} 

}

return 0;

}