话说这题TLE了n次，我就知道是输入输出问题，刚开始真心相当无奈（套用大牛代码也TLE），后来突然想起来改用C++提交，怒AC。。。（看来大牛平常也用C++提交啊！g++就是一个坑爹编译器.....)
公式推出来很简单，根据题意，F(n)=F(n-1)+2F(n-2)+...+nF(1)+1，试了几组测试数据发现F(n)和兔子数列有关，F(N)是兔子数列的第n-1项，有此得F(n)=3F(n-1)-F(n-2)，后来通过最初的公式推导出了这个。。。果断用矩阵快速幂推，发现超时，这是突然看到数据量很大，果断想到了斐波那契模一个数的循环问题。。现在就这个问题证明一下：若斐波那契数列模一个数存在循环节，则循环节必从1开始，且循环最后的两个数必是1和0。。。证明用反证法：若循环节不在第一位，设F(x)=f(y),f(x+1)=f(y+1)，则可以证明F(x-1)=f(y-1)，与之前假设F(x-1)!=f(y-1)不符合，所以循环一定在第一个，也就推出循环后两个数是1和0。。。初始化的时候，用F(n)=3f(n-1)-f(n-2)初始化，循环节折半为75000，代码略

以上图为例，提取规格内容为500x3+200存储在数据库表里，当产品数量级大时，可以循环运行下面代码计算规格总数，便于求规格均价的分析场景。

使用SP_EXECUTESQL方法

--1、生成对应字段的计算公式
drop table ##T1
;with x1 as (
	select row_number()over(order by id) ids,id,'select @t='+replace(replace(replace(replace(cc,'ml',''),'g',''),'x','*'),'×','*') sql from (
		select id,title,replace(bb,substring(ctool.dbo.GetRegexMatchGroups(bb,'([\u4e00-\u9fa5]+)',0,100),1,100),'')cc from (
		select *,replace(aa,substring(ctool.dbo.GetRegexMatchGroups(aa,'([\u4e00-\u9fa5]+)',0,100),1,100),'') bb
		from test.dbo.vivian_guige_temp  
		) b 
	) c where cc not like '%[0-9][lk]%'
)
select * into ##T1 from x1
select * from ##T1  --ids便于做循环判断，id是原始数据的唯一标志，便于匹配回原结果表

--2、生成临时表存放循环计算的字段结果
drop table ##T2
create table ##T2(id int,specs int)

declare @id int
declare @a nvarchar(100)
declare @name int
declare @i int
declare @j int
set @j=1
select @i=max(ids) from ##T1 
while @j<=@i  --循环条件，确定需要循环的次数
begin
	select @id=id,@a=sql from ##T1 where ids=@j
	EXEC SP_EXECUTESQL @a, N'@t int output', @name OUTPUT;
	insert into ##T2 values(@id,@name)
	set @j=@j+1
end

运行结果：

1、运行临时表##T1查询的结果



2、循环计算后存储在临时表##T2的结果



备注：可以上网详细了解SP_EXECUTESQL的用法，博主也是试了很多种方式才求出来结果，如果有更好的方法实现可以评论告知一下，感激~

约瑟夫问题
N个人站在一个等待被处决的圈子里。第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个人就是最后的胜利者。
问题描述
输入：n，m。其中n为总人数，依次编号为0，1…n，m为被处决的报数数值。

输出：最后活下来人的编号。
解决方案
1.循环单链表法
用循环单链表去模拟这个过程。n个人看做n个链表节点，节点1的value为1，节点1的next指向节点2，节点2的value为2，节点2的next指向节点3，…，节点n的value为n，节点n的next指向节点1，构成一个循环单链表。然后从节点1开始报数，如果报数到m就被删除，最后剩下的那个节点的value就是活下来人的编号。python代码如下:
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def create_linkList(n):
    head = Node(1)
    pre = head
    for i in range(2, n+1):
        newNode = Node(i)
        pre.next= newNode
        pre = newNode
    pre.next = head
    return head


n = 8 # 总的个数
m = 3 # 数的数目
if m == 1: # 如果被处决的报数为1，直接输出最后一个值
    print(n)
else:
    head = create_linkList(n)
    pre = None
    cur = head
    while cur.next != cur: # 终止条件是节点的下一个节点指向本身
        for i in range(m-1):
            pre = cur
            cur = cur.next
        pre.next = cur.next
        cur.next = None
        cur = pre.next
    print(cur.value)

2.公式法
递推公式：

$f(n,m) =(f(n-1,m)+m)\ mod\ n$

$f(1,m) = 0$

代码如下：
n = 8 # 总的个数
m = 3 # 数的数目
if m == 1: # 如果被处决的报数为1，直接输出最后一个值
    print(n)
else:
    i = 0
    a = list(range(n))
    while len(a) > 1:
        i =(i+2)%len(a)
        del a[i]
    print(a[0] + 1)

参考：

约瑟夫问题-维基百科

指数循环节问题：需要对指数进行降幂处理才能计算

比如：ans = 2 ^ n % mod 

 其中1 <= n <= 10^100000和1 <= m <= 10^6

这里由于n很大，所以需要进行降幂。那么实际上有如下降幂公式

A^B mod C =  A ^ (B % phi(C) + phi(C)) mod C;

有了上述公式，很多题目就可以迎刃而解了。



#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N=1000005;
typedef long long LL;

char str[N];

int phi(int n)
{
    int rea = n;
    for(int i=2; i*i<=n; i++)
    {
        if(n % i == 0)
        {
            rea = rea - rea / i;
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1)
        rea = rea - rea / n;
    return rea;
}

LL multi(LL a,LL b,LL m)
{
    LL ans = 0;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = (ans + a) % m;
            b--;
        }
        b >>= 1;
        a = (a + a) % m;
    }
    return ans;
}

LL quick_mod(LL a,LL b,LL m)
{
    LL ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = multi(ans,a,m);
            b--;
        }
        b >>= 1;
        a = multi(a,a,m);
    }
    return ans;
}

void Solve(LL a,char str[],LL c)
{
    LL len = strlen(str);
    LL ans = 0;
    LL p = phi(c);
    if(len <= 15)
    {
        for(int i=0; i<len; i++)
            ans = ans * 10 + str[i] - '0';
    }
    else
    {
        for(int i=0; i<len; i++)
        {
            ans = ans * 10 + str[i] - '0';
            ans %= p;
        }
        ans += p;
    }
    printf("%I64d\n",quick_mod(a,ans,c));
}

int main()
{
    LL a,c;
    while(~scanf("%I64d%s%I64d",&a,str,&c))
        Solve(a,str,c);
    return 0;
}